c++ - 如何在这个 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 及其自身的条件清楚地表明代码只不过是对排序列表的线性搜索。