如何在这个 while 循环中找到迭代次数 - 操作计数

Question

我对如何计算 while 循环的操作计数特别是迭代次数感到困惑。 我确实了解如何找到常规循环（从 0 到 n）以及二进制搜索 (log2n) 的迭代次数，但这段代码利用了 true 和 false 的情况。迭代次数取决于 "more" 是否为真且 "found" 是否为假。

最坏的情况是什么？找不到该项目？ 在下面的代码中，注释部分是该行的操作计数。

List为N个节点的链表结构：

void FindItem(Node *list, Item item, Node *&loc, bool &found){
    bool more = true;                 // 1
    loc = list; found = false;        // 2
    while (more && !found) {          // (number of iterations)
        if (item < loc->info)         // 2 * (number of iteration)
            more = false;             // (0 or 1)*number of iterations
        else if (item == loc->info)   // 2 * (number of iteration)
            found=true;               // (0 or 1)*number of iterations
        else {
            loc = loc->next;          // (0 or 2) * (number of iteration)
            more = (loc != NULL);     // (0 or 2)*number of iterations
        }
    }
}

Answer 1

这看起来像是学校练习题或家庭作业题。 事实上，您需要在纸上回答，这几乎证实了这一点。

所以你要找的可能是“Big O”的复杂度。 在那种情况下，您看到的是一个简单的 0 .. n 循环，您声称知道它，因为循环最多可以 运行 遍历整个列表。

条件变量的名称 more 及其自身的条件清楚地表明该代码只不过是对排序列表的线性搜索。