algorithm - 理解运行时函数

Question

我正在为一个困难的考试做一些自学(对我来说)，我无法掌握使用 T(n) 函数的算法执行时间的概念。

例如:

i = 1;                 // c1  1

sum = 0;               // c2  1

while (i <= n) {       // c3 n+1

    i = i + 1;         // c4 n

    sum = sum + i;     // c5 n

}

成本计算:

Total Cost = c1 + c2 + (n+1).c3 + n.c4 + n.c5

T(n) = an^2 + bn + c

找到总成本就足够了吗？

请原谅我的笨拙，任何资源也会有所帮助。

Answer 1

找到确切的运行时间通常是没有用的，因为它取决于很多因素，包括您的编译器优化、您的硬件架构、您运行的程序数量、您的操作系统等等。\
一个简单的例子:需要多少时间:

for (int i = 0; i < 16; i++) 
   c[i] = a[i] + b[i]'` 

答案是——视情况而定。例如，许多现代机器允许在一条指令中进行向量加法，这比迭代和加法花费的时间要短得多。

由于上述原因，我们很少关心确切的理论时间，而我们 big O notation 相反，或者 - 根据实际性能比较某些算法的运行 - 使用 statistical tests 。

您的代码在大 O 表示法下的复杂度是 O(n) - 因为它涉及迭代 n元素，并为每个元素做一些恒定的时间修改。