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

Question

我试图从我教授的讲义中理解复杂性 class 算法，但我仍然无法掌握它。

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。

据我所知，它的复杂性 class 是 N^2，因为它是其余部分中增长最快的。我们忽略常量，因为它们在无穷大时无关紧要。

不过，我想知道他是怎么得到常量的。

我不明白他是怎么得到+6的，这个函数调用一次，运行一共才6次，到底是什么意思？我看到 int base = 0 只创建一次，因为它属于外部 for 循环。

编辑：所以我发现 + 6 只是这个函数需要的最低限度运行。如果 for 循环只执行一次……那么总行数是多少？好吧，我们复制了 a[] 和 int N，然后我们有了 for 循环和 if 语句。所有的加起来都是 6.

12N 呢？

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
}

关于 memory/register/direct 访问或 ALU 操作有多少个周期，我做了 狂野的假设 。 M = ~ (N^2)/2（抱歉懒得从系列总和中获取实际计数）是内循环迭代的次数。因此，当我将所有内容加在一起时，我得到：

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

这和你的表达很接近。由于我使用了不准确的 M 并且不知道其背后的架构，因此结果可能会有所改变，可能有利于您的表达。因此函数 init 和 return 占 ~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

要使其准确，您应该：

准确计算M
获取
将代码分解为原子操作

区分direct/memory(heap/stack)/注册访问（甚至可能read/write ), ALU 操作和更多...例如 swap(a,b) { c=a; a=b; b=c; } 如果它不是由 Xoring 完成...现在你可以像我试过的那样数周期......

例如看这里 Machine cycle timings for Z80 我的 Zilog Z80A 完整指令集的 link 和机器周期计时。所以你可以看到每种指令有多么不同。对于正在学习这些东西的platform/architecture，你应该有类似的东西。

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

Explain why this unsimplified complexity expression is this?

c++

algorithm

complexity-theory

time-complexity