为大哦复杂性嵌套循环

本文介绍了为大哦复杂性嵌套循环的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 for(int i = 0; i < n; i++) { for(int j = 0; j < i; j++){ //do swap stuff, constant time } }

我读到单个for循环为O(N)，遍历两次将使其变为O(n ^ 2).我观看了相关教程，该教程显示每个操作的单位为1-O(1).我想详细了解O(n ^ 2)是如何实际出现的.我试图为每个语句做数学运算，但是我认为我做得不对.如果有人能从字面上告诉我循环嵌套如何成为O(n ^ 2)，我将不胜感激.预先感谢

I read that single for loop is O(N) and traversing it twice will make it O(n^2) I watched related tutorials which shows that each operation takes unit of 1 - O(1). I would like see in details how O(n^2) actually came up. I tried to do math for each statement but I believe I am not doing it right. I would appreciate if someone can literally show me how nested for loop becomes O(n^2). Thanks beforehand

推荐答案

您提到的

每个取1的单位-O(1)

Each takes unit of 1 - O(1)

因此，内部循环的每次迭代都需要1、2、3，...，n个单位时间.

So each iteration of the inner loop takes 1, 2, 3, ... , n unit time.

total_time = 1 + 2 + 3 + ... + (n-2) + (n-1) + n

倒车

total_time = n + (n-1) + (n-2) + ... + 3 + 2 + 1

添加

2 * total_time = (n+1) + (n+1) + (n+1) + ... + (n+1) + (n+1) + (n+1)

共有n个词

2 * total_time = (n+1) * n => total_time = (n+1) * n / 2 => total_time = n^2 / 2 + n / 2

由于O复杂度大，忽略了较低的项和常数.

Lower terms and constant coefficients are neglected for big O complexity.

结果

O(n ^ 2)