时间戳

首页 > 解决方案 > 如何在这个while循环中找到迭代次数 - 操作计数

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

问题描述

我对如何对 while 循环特别是迭代次数进行操作计数感到困惑。我确实了解如何找到常规循环（从 0 到 n）以及二进制搜索（log2n）的迭代次数，但这段代码利用了真假的情况。迭代次数取决于“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
        }
    }
}

标签： c++complexity-theory

解决方案

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

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

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

推荐阅读