时间戳

首页 > 解决方案 > 这两个while循环的时间复杂度

time-complexity - 这两个while循环的时间复杂度

问题描述

x = 1;
while(x<n)
{
    x = x + n / 10;
    m = n*n
    y = n;
    while(m>y)
    {
        m=m-100;
        y=y+20;
    }
}

我解决的方法：我们每次都加到n的x 1/10，所以不管n有多大，我们做的重复次数总是10。内循环是从n到n^2，并且其中的每个变量都是线性增加的，所以内循环应该是 O(n)

因为外循环是 O(1)，所以我们得到所有函数的 O(n)。但该问题的可选答案是：O(n^2), O(n^3), O(n^4), O(nlogn)

我错过了什么？谢谢。

标签： time-complexity

解决方案

外循环运行恒定次数（10 次）是正确的，但您对内循环的推理并不完全正确。您说内部循环的每次迭代都有一个“线性增加”，如果是这种情况，那么整个函数在 O(n) 中运行是正确的，但事实并非如此。尝试从这里弄清楚，但如果你仍然卡住：

内部循环必须根据 m 和 y 之间的差异来弥补 n^2 和 n 之间的差异。每次迭代时，m 和 y 之间的差异会减少一个常数：120，而不是线性量。因此内循环运行 (n^2 - n)/120 次。将外循环运行的次数乘以内循环运行的次数，我们得到：

O(10) * O((n^2 - n)/120) 
= O(1) * O(n^2) 
= O(n^2)

推荐阅读