算法 - 比较性能

Question

假设我有 3 个算法 A、B 和 C 来处理 n 条记录。

algorithm A takes 80n + 40 steps
algorithm B takes n^2 + 30n steps
algorithm C takes 2^n steps

决定哪些算法在执行时最有效

i)  10 < n < 50 

我解决这个问题的方法是假设 n 等于一个值，例如

对于 i) 假设 n = 20

所以

algo A - 80(20) + 40 = 1640  steps
algo B - 20^2 = 400 steps
algo C - 2^20 = 1048576 steps

因此算法 B 是最有效的。

我不太确定我是否正确评估了这 3 种算法的性能，因为我只是用一个值代替 n，而不是使用大 O 表示法？

请指教。谢谢

Answer 1

Big-O 表示法处理任意大的 n，即为了计算 O(n)，应该计算 n--> 无穷大的表达式。在你的情况下，n 是给定的，因此可以精确计算总运行时间，完全按照你的方式计算。