while循环的时间复杂度是多少？ [英] What is the time complexity of while loops?

问题描述

我试图找到while循环的时间复杂度，但我不知道从哪里开始。我知道如何找到for循环的复杂性类，但是当涉及while循环时，我会完全迷失方向。任何有关从何开始的建议/提示？

以下是一个问题示例：

  x = 0; 
 A [n] =长度为n的某个数组； 
 while（x！= A [i]）{
 i ++; 
} 
  

解决方案

当您必须做某事时 n 次，则必须执行 n 次。您可以使用 for 循环， while 循环或您的编程语言（或伪代码！）提供的任何内容。
粗略的O标记表示您必须做的工作量，而不在乎您的工作方式（有点不太粗略，它评论了需要完成的工作量是如何增长的

请继续阅读以获取详细信息。

---

<我想你在这里使事情混乱。
for 和而是表示要重复操作的编程语言构造。

算法分析与实现语言无关，并且不关心表达算法时使用的实际构造。

请考虑以下内容：

  1。输入n 
 2.做OperationX n次
  

Big O标记机制可帮助您发表评论以上操作的复杂性。这在许多情况下都有帮助。例如，它可以帮助您将上述操作的运行时间与以下内容进行比较：

  1。输入n 
 2.输入m 
 3.重复m次OperationX n次。 
  

Big O符号会告诉您前者是O（n），后者是O（ m * n）（假设 OperationX 需要一个恒定的时间）。

您可以使用循环结构编写代码

  for（int i = 0; i  operationX; 
} 
  

是第一个操作，

  i = j = 0; 
 while（i< n）{
 j = 0; 
 while（j< m）{
 operationX; 
 j ++; 
} 
 i ++; 
} 
  

秒。大的O标记并不真正在乎是否更改了for和while。

---

  A [n] =长度为n的某个数组； 
 for（x = 0; x！= A [i]; i ++）{
 
} 
  

是用于以相同的复杂度（ O（n））。

I'm trying to find the time complexity of while loops and I have no idea where to begin. I understand how to find the complexity class of for loops, but when it comes to while loops, I get completely lost. Any advice/tips on where to begin?

Here is an example of a problem:

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

解决方案

When you gotta do something n times, you have to do it n times. You can use a for loop, a while loop or whatever that your programming language (or pseudo code!) offers. Crudely, big O notation comments on the amount of work you have to do, and doesn't care about how you do it (somewhat less crudely, it comments on how the amount of work that needs to be done grows with the growing input).

Keep reading for the details.

---

I think you are confusing things here. for and while are programming language constructs to express operations that are to be repeated.

Algorithm analysis is agnostic of the language of implementation, and doesn't care about the actual constructs you use while expressing the algorithm.

Consider following:

1. Input n
2. Do OperationX n times

The Big O notation machinery helps you in commenting on the complexity of the above operation. This helps in many cases. For example, it can help you in comparing the runtime of the operation above with the following:

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

The Big O notation will tell you that the former is O(n) and the latter is O(m * n) (assuming OperationX takes a constant time).

You can write the code using the loop construct of your choice, it doesn't matter.

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

Is the first operation, and

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

the second. The big O notation doesn't really care if the for and while was switched.

---

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

}

Is a for re-write of your question with the same complexity (O(n)).

这篇关于while循环的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！