二次算法的时间复杂度

Question

对于我的编程和算法设计考试，我必须熟悉时间复杂度和 Big-Oh 表示法。我理解大部分内容，但后来我遇到了这个问题，我的解决方案似乎相当简单；但我不明白哪些步骤是必要的。有人可以澄清所采取的步骤吗？

锻炼：

处理时间为 T(n) = cn^2 的二次算法花费 T(N) 秒来处理 N 个数据项。假设 N = 100 且 T (N) = 1 ms，处理 n = 3000 个数据项将花费多少时间？

给出的解决方案：

常数因子 c = T(N)/(N^2)，因此 T(n) = T(N) * (n^2)/(N^2) = n^2/10000 并且 T (3000) = 900毫秒

Answer 1

这是一个非常简单的数学问题：

\n\n

如果T(n) = cn\xc2\xb2然后T(100) = 1ms​

\n\n

T(100) = c * 100\xc2\xb2\n       = c * 10,000\n       = 1ms\n

\n\n

因此求解c给出：

\n\n

c = (1/10,000)ms\n

\n\n

然后可以用它来计算T(3000)：

\n\n

T(3000) = (1/10,000)ms * 3,000\xc2\xb2\n        = (1/10,000)ms * 9,000,000\n        = (9,000,000 / 10,000)ms\n        = 900ms\n

\n