二次算法的时间复杂度

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

练习：

的二次算法的处理时间T（N）= CN^2花费T（N）秒用于处理N个数据项。假设N = 100且T（N）= 1ms，将花费多少时间来处理n = 3000个数据项目？

鉴于溶液：

常数因子c = T（N）/（N^2），因此T（N）= T（N）*（N^2）/（N^2）= n^2/10000和 T（3000）= 900ms

我完全和'n'和'N'混淆。两者都是数据项的数量，但它们有所不同。 –

N和n看起来是一样的。我认为N用来表示一个特定的例子。 –

真的吗？ “假设N = 100，需要花费多少时间来处理n = 3000个数据项” –

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

如果T(n) = cn²和T(100) = 1ms然后

T(100) = c * 100² 
     = c * 10,000 
     = 1ms

因此求解c给出：

c = (1/10,000)ms

这可以被用来计算T(3000)：

T(3000) = (1/10,000)ms * 3,000² 
     = (1/10,000)ms * 9,000,000 
     = (9,000,000/10,000)ms 
     = 900ms

2014-01-25 12:40:37 Iridium

哦哇，我只是看错了方式......哈哈，非常感谢！ *脸红* – user3235058

它是直截了当的。您有N = 100，T(N) = 1。所以c = T(N)/N^2 = 1/10000。

然后你做T(3000) = 1/10000 * (3000^2) = 900。

2014-01-25 12:40:01

这与Big-Oh notation，甚至计算机科学没有任何关系。所有你需要的是基础代数。考虑到T（n）= cn^2对于某些c，T（100）= 0.001，T（3000）是多少？

0.001 = T(100) = c (100*100) = 10000c 
    c = 10^-7 

    T(3000) = c n^2 = 10^-7 * 3000 * 3000 = 0.9

2014-01-25 12:40:27 meriton

回答