while循环的时间复杂度是多少？

Question

我试图找到while循环的时间复杂性,我不知道从哪里开始.我理解如何找到for循环的复杂性类,但是当涉及while循环时,我完全迷失了.关于从哪里开始的任何建议/提示？

这是一个问题的例子:

x = 0;
A[n] = some array of length n;
while (x != A[i]) {
   i++;
}

Answer 1

当你要做某些事情时n,你必须做到这一点n.您可以使用for循环,while循环或您的编程语言(或伪代码!)提供的任何内容.粗略的,大O符号评论你必须做的工作量,并不关心你是如何做的(稍微粗略一点,它评论了需要做的工作量随着不断增长的投入而增长) .

继续阅读细节.

我觉得你在这里混淆了一些事情. for并且while是编程语言构造以表达要重复的操作.

算法分析与实现语言无关,并不关心在表达算法时使用的实际构造.

考虑以下:

1. Input n
2. Do OperationX n times

Big O表示法机器可以帮助您评论上述操作的复杂性.这在很多情况下都有帮助.例如,它可以帮助您将上述操作的运行时与以下内容进行比较:

1. Input n
2. Input m
3. Repeat m OperationX n times.

Big O表示法将告诉您前者是O(n)而后者是O(m*n)(假设OperationX需要一个恒定的时间).

您可以使用您选择的循环结构编写代码,这没关系.

for(int i = 0; i < n; i++) {
    operationX;
}

是第一次操作,和

i = j = 0;
while(i < n) {
    j = 0;
    while(j < m) {
      operationX;
      j++;
    }
    i++;
}

第二.如果for和while被切换,那么大的O符号并不在乎.

A[n] = some array of length n;
for(x = 0;x != A[i];i++) {

}

是否以for相同的复杂度(O(n))重写您的问题.