c++ - 计数操作 - 嵌套循环中有多少个运算符？

Question

我目前正在做一个关于 Big O 的个人项目，以及我们如何使用线性方程等对不同的算法进行分类。因为对于这个学校项目，我想重点强调我们在课堂上学到的东西来提高我的分数（二次方程等），找到我如何使用数学来找到大 O 可能会很好。

根据我所学到的，我首先计算代码中运算符的数量。然后，根据它的时间复杂度，我必须创建一个满足我们算法的方程；例如，如果我有一个 O(n) 的算法，我的方程将类似于 y = mx+b。

这真的很容易，但是对于具有嵌套循环的二次函数或算法，它就更难了......假设我有以下代码......

void printAllPairs()
{
    //int n = 5; just using n to represent our array size, but for now we'll initlalize it to a value

    for (int i = 0; i < n; i++) 
    {
        for (int j = 0; j < n; j++)
        {
            std::cout << i << "," << j << "\n"; 
        }
    }
}

我知道这个算法是 O(n^2)，我也知道将 O(n^2) 记为 O(n^2+an+b) 或将 O(n) 记为 O(mn+b) 是不好的做法，但是我如何用二次方程（例如 x^2 + ax + b 或类似的东西）来表示这个算法？我知道我有两个常量（第 3 行和第 5 行中的两个赋值运算符），但是在“int j = 0”中找到的运算符是否也被视为常量？由于这是一个嵌套循环，所以每次运行第二个循环时都必须再次运行 j = 0，对吗？

使用 O(n) 方程，这非常简单，因为我可以轻松识别哪些运算符是常数和系数，也就是哪些运算符受或不受 n 影响。

关于如何将 printAllPairs() 算法表示为二次方程的任何帮助？对不起，如果这对你们来说似乎很容易，但是一位高中生在这里需要帮助。

编辑：

标签： c++algorithmbig-o

Answer 1

首先，我想澄清一些可能是误解的事情（尽管我可能对你的问题读了很多）。O(n^2)不是 . 的速记或简化O(n^2 + an + b)。相反，它们指的是完全相同的东西。O(n^2 + alog(n))也是同样的事情，无数其他的表达方式也是如此。使算法二次的不是复杂度是二次多项式，而是复杂度最终不会比an^2某些特定的增长更快a。这就是 big-O 的价值：我们不必担心对复杂性的所有可能贡献，而是可以专注于一般形状。

Big-O 有太多细节

好的，关于我认为你的问题的核心，即如何明确常量。我通常不建议在实践中这样做，但从技术上讲，这是真正的交易。

让我们将问题分解为多个部分并构建完整的问题。首先，算法中最简单的部分：

std::cout << i << "," << j << "\n";

这不依赖于n，它的时间复杂度以某个常数为界。我们称它为常量a。所以我们这条语句的总时间复杂度是：

t0 = a

酷，漂亮，简单。

现在让我们介绍最里面的循环：

for (int j = 0; j < n; j++)
{
    std::cout << i << "," << j << "\n"; 
}

就时间复杂度而言，这个循环涉及：

1. n重复std::cout我们刚刚分析的常量语句。
2. n重复一些不断的记账工作（如增量、比较、跳转）。我们称之为簿记复杂性b1。
3. 一些额外的恒定工作（例如初始化j）。我们称之为复杂性b2。

总而言之，我们的时间复杂度现在看起来像这样：

t1 = n * (t0 + b1) + b2
   = n * (a + b1) + b2

这遵循 中的线性多项式的一般形式n。

现在我们再次做同样的思考过程。

1. n我们刚刚分析的（线性）循环的重复。
2. n重复一些我们称之为的持续簿记工作c1。
3. 一些额外的持续工作，我们称之为c2.

所以这个循环的时间复杂度是：

t2 = n * (t1 + c1) + c2
   = n * ((n * (a + b1) + b2) + c1) + c2
   = n^2 * (a + b1) + n * (b2 + c1) + c2

所以我们看到算法是O(n^2 * (a + b1) + n * (b2 + c1) + c2)，这当然等价于O(n^2)。

实践中的大 O

在这里，我们就 Big-O 的实际计算提出一些建议，这将为您省去很多麻烦。我将带您回到“big-O 的值”，即常量和非显性项根本不重要，所以甚至不必费心去跟踪它们。仅此一项就可以为您省去很多麻烦。

再一次，让我们打破这个问题。您会看到分析看起来就像上一节一样，但噪音大大降低。

我们再次从单个语句开始：

std::cout << i << "," << j << "\n";

由于这不依赖于n，我们称其为常数。即，时间复杂度为O(1)。

现在我们介绍最里面的循环：

for (int j = 0; j < n; j++)
{
    std::cout << i << "," << j << "\n"; 
}

我们有：

1. n重复O(1)我们刚才分析的陈述。
2. n重复一些O(1)簿记工作。
3. 一些额外的O(1)工作。

所以这个循环有时间复杂度O(n * 1 + n * 1 + 1)，相当于O(n).

现在最外层循环：

1. nO(n)我们刚刚分析的循环的重复。
2. n重复一些O(1)簿记工作。
3. 一些额外的O(1)工作。

所以这个循环有时间复杂度O(n * n + n * 1 + 1)，相当于O(n^2).