解释为什么这个未简化的复杂表达式是这样的？

Question

我试图从我的教授讲义中理解复杂度算法，但我仍然不太明白。

void sort(int a[], int N) { //N is the length of the array
   for (int base=0; base<N; ++base)
      for (int check=base+1; check<N; ++check)
         if (a[base] > a[check])
            std::swap(a[base], a[check]);
}

在他的笔记中，他说这个表达式是8N^2 + 12N + 6。

据我完全理解，这个复杂度类别是N^2，因为它是增长速度最快的。我们忽略常数，因为当趋于无穷大时它们是不相关的。

然而，我想知道他是如何得到这些常数的。

我不明白他是如何得到加号后面的6的。当此函数被调用一次时，有哪些内容仅运行了总共6次？我看到int base = 0只创建了一次，因为它属于外部for循环。

编辑：所以我发现+6是这个函数必须运行的最低要求。在只执行for循环一次的情况下......那么总行数呢？好吧，我们复制了a[]和int N，然后我们有我们的for循环和if语句。所有东西加起来总共是6。

那么12N呢？

- Jacob Macallan

---

这段代码不就是冒泡排序吗？我不知道它与其他部分有什么关系（为什么需要 int N？你已经可以通过类似 a.Length 的方式获取到这个信息了）。 - M. Schena

这里唯一正确的是*n²*时间复杂度。所有的常数都是虚构的。这里的6指的是什么？6个什么？在哪个平台上？既然常数是虚构的，你可以想象内部循环在每次迭代中运行12次或任何其他数。这有点胡说八道，我必须承认。 - Ami Tavory

只有在假设算法中的基本元素执行时间后，您才能获得这些常量。我们不知道您的教授是如何定义这些常量的。然而正如@AmiTavory已经指出的那样，在实践中这是无关紧要的。 - Henry

Answer 1

如Ami Tavory所建议的那样，这看起来像胡说八道。经过更仔细的观察，它仍然非常奇怪，因为该表达式混合了非常不同的操作周期，就像它是原子的一样... 如果我忽略相关性，我会这样看待它：

void sort(int a[], int N) {                    // ?T
   for (int base=0; base<N; ++base)            // 1 +(3+2)N
      for (int check=base+1; check<N; ++check) // 2N+(3+2)M
         if (a[base] > a[check])               // (2+1+2)M
            std::swap(a[base], a[check]);      // (2+2+2)M
}

我对内存/寄存器/直接访问或ALU操作所需的循环次数做出了荒谬的假设。 M = ~ (N^2)/2（抱歉，懒得从级数求和中获取实际计数）是内部循环迭代次数。因此，当我将所有内容相加时，我得到：

16*(N^2)/2+7N+1+?
8*N^2 + 7N + 1+?

这与您的表达式非常接近。由于我使用了不准确的M，并且不知道背后的架构，因此结果可能会略微改变，可能会更有利于您的表达式。因此，函数的初始化和返回占用了~5个周期。如果我变得更疯狂一些：

int a[]; // 2 // heap -> reg
int N;   // 2 // heap -> reg
 {}      // 1 // stack return (I would guess it should be also 2)

所以我得到了：

8*N^2 + 7N + 6

反对你的：

8*N^2 + 12N + 6

为了使它更准确，您应该：

1. 精确计算M
2. 获取适用于此架构的操作时间

3. 将代码分解为原子操作

   区分直接/内存(heap/stack)/寄存器访问（甚至可能是读/写）、ALU操作等等...例如，swap(a,b) { c=a; a=b; b=c; }如果没有通过Xor完成...现在您可以像我尝试的那样计算周期...

   例如，在这里查看Machine cycle timings for Z80，其中有一个链接到我的Zilog Z80A完整指令集和机器周期计时。因此，您可以看到每种类型的指令实际上有多么不同。您应该为您正在学习此内容的平台/架构拥有类似的东西。

- Spektre

---

非常感谢您的回复。我给您的场景是在他的讲义中，无论我看了多少遍都无法理解。知道这几乎是胡说八道让我感到安慰。我至少知道现在我理解了复杂度类。 - Jacob Macallan