algorithm - 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.

大 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)) 重写您的问题。