我试图从我的教授讲义中理解复杂度算法,但我仍然不太明白。
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呢?