为大哦复杂性嵌套循环 [英] Nested for loop in Big Oh Complexity

问题描述

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)

这篇关于为大哦复杂性嵌套循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！