while（多条件）复杂度分析

Question

很明显，a while (i < k) 将 运行 k 项 -- 或不，取决于 i 的起始值。

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

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

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

Answer 1

上述循环的时间复杂度为O(k)，与found变量无关。在最坏的情况下，计数将 运行 到 k，这也是平均情况。