Big O for while循环

Question

前几天我对我的任务提出了这个问题,但我仍然不确定我是否正确.

for(int i =1; i <n; i++)   //n is some size
{             
    for(j=1; j<i; j++)
    {
        int k=1;

        while (k<n)
        {
           k=k+C;   //where C is a constant and >=2
        }
    }
}

我知道嵌套for循环是O(n ^ 2)但我不确定while循环.我假设整个代码都是O(n ^ 3).

Answer 1

    int k=1;

    while (k<n){
       k=k+C                    //where C is a constant and >=2
    }

这将采取(n-1)/C以下步骤：写u = (k-1)/C。那么，k = Cu + 1 并且语句变为

u=0;
while(u < (n-1)/C) {
    u=u+1
}

因此 while 循环是O(n)（因为C是常数）

编辑：让我尝试以相反的方式解释它。

从虚拟变量开始u。循环

u=0;
while(u < MAX) {
    u = u+1
}

运行MAX次数。

当你 let 时MAX = (n-1) / C，循环是

u=0;
while(u < (n-1)/C) {
    u=u+1
}

这需要(n-1)/C时间。

现在，检查u < (n-1)/C相当于C*u < n-1or C*u + 1 < n，因此循环相当于

u=0;
while(C*u + 1 < n) {
    u=u+1
}

现在，假设我们用变量 重写了这个循环k = C * u + 1。然后，

u=0;
k=1; // C * 0 + 1 = 1

循环看起来像

while(C*u + 1 < n) {
while(k < n) {

内部条件是

    u=u+1
    k=k+C //C * (u+1) + 1 = C * u + 1 + C = old_k + C 

把它们放在一起：

    int k=1;

    while (k<n){
       k=k+C
    }

采取(n-1)/C措施。