While(多条件)复杂度分析 [英] While (multiple conditions) Complexity Analysis

问题描述

很明显，while (i < k) 将运行 k 个项目——或不运行，取决于 i 的起始值.

It is obvious that a while (i < k) will run k items -- or not, depending on the starting value of i.

但是如果我有一个 while 循环，例如:

But what if I have a while loop such as:

while (counter != k && !found) {
   if (some condition)
     found = true;
   else
     counter++;
}

如果我不知道 found 何时被设置为 true，我将如何计算最坏情况下的时间复杂度?

How would I calculate the worst case time complexity if I don't know when found will be set as true?

推荐答案

上述循环的时间复杂度为 O(k) 并且与 found 变量.在最坏的情况下，计数会一直运行到 k，这也是平均情况.

The time complexity of the above loop will be O(k) and it is irrespective of the found variable. As in the worst case the count will run till k and that will be the average case as well.

这篇关于While(多条件)复杂度分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！