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

ShippyDippy

我对如何在while循环中进行操作计数（特别是迭代次数）感到困惑。我确实了解如何找到常规循环（从0到n）以及二进制搜索（log2n）的迭代次数，但是这段代码利用了true和false的情况。迭代次数将取决于“更多”为true和“找到”为false。

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

列表是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
        }
    }
}

列夫·M。

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

因此，您正在寻找的可能是“ Big O ”复杂性。在这种情况下，您正在看一个简单的0 .. n循环，您声称知道该循环，因为该循环最多可以遍历整个列表。

条件变量的名称及其more自身的条件是一个清晰的线索，表明该代码不过是对排序列表的严格搜索。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。