big-o - 计算大O

Question

所以我想为这段代码计算大 O，但我不确定如何处理它。一些帮助开始将不胜感激。

`

            for ( i = 1 ; i * i < n ; i++){
                for ( j = 1 ; j < n ; j++)
                {
                  ...
                }
            }
            for ( i = 1 ; i < n ; i++){
                for ( j = i % 5 ; i + j < 2000; j++)
                {
                  ...
                }

`

Answer 1

好的，所以我们从第一个内部循环开始，看看它是O(n). 然后，i从 1 到平方根 n，因此该循环的复杂度为O(sqrt(n))。然后我们将它们相乘以找到第一个嵌套循环的复杂度，即O(n * sqrt(n)).

第二个外循环的复杂度n为 ，内循环运行定义的次数（不依赖于 n），因此总复杂度为O(n * sqrt(n) + n)。

Answer 2

大 O 是最坏的情况，在这种情况下是 N^2，因为您在第一个 for 循环内有一个嵌套的 for 循环。

第二组 for 循环只是 N 中的大 O，因为内部 for 循环最多会运行 2000 次，而且在事情的范围内非常小，尤其是当 N 很大时。