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

Question

我试图找出 while 循环的时间复杂度，但我不知道从哪里开始。我了解如何找到 for 循环的复杂度 class，但是当涉及到 while 循环时，我完全迷失了。 advice/tips 从哪里开始？

这是一个问题的例子：

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

大 O 符号机制可帮助您评论上述操作的复杂性。这在很多情况下都有帮助。例如，它可以帮助您将上面操作的运行时间与以下操作进行比较：

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

大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++;
}

第二个。大 O 表示法并不真正关心 for 和 while 是否被切换。

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

}

是 for 以相同的复杂性 (O(n)) 重写您的问题。

What is the time complexity of while loops?