时间复杂度上的大写 N 与小写 n
Capital N vs small n in time complexity
我遇到了以下问题，这让我很困惑：
A quadratic algorithm with processing time T(n) = cn2 spends T(N)
seconds for processing N data items. How much time will be spent for
processing n = 5000 data items, assuming that N = 100 and T(N) = 1ms?
N和n在时间复杂度上有什么区别？
大写N与小写n在时间复杂度上没有特殊含义。在这种情况下 n 和 N 只是用作同一个变量的不同值，如果他们给你 x.[=44 而不是 N 就没有区别=]
Important, when I use A => B, the => arrow means "A equals to B", or if you prefer "A ends up being B"
现在，考虑到原始的二次函数 T(n) = c*n^2
- 如果
N = 100 和 T(N) = 1ms 那么他们告诉你 T(100)
= 1ms => 1ms = c * 100^2.
- 你从前面的陈述中推断出的是
1ms = c * 100^2 =>
c = 1ms / 100^2.
现在只需将原公式T(n) =
cn2（即n = 5000）中的c和n替换为：
T(5000) = (1/100^2) * 5000^2 => T(n) = 2.500ms => T(n) = 2,5s
我遇到了以下问题，这让我很困惑：
A quadratic algorithm with processing time T(n) = cn2 spends T(N) seconds for processing N data items. How much time will be spent for processing n = 5000 data items, assuming that N = 100 and T(N) = 1ms?
N和n在时间复杂度上有什么区别？
大写N与小写n在时间复杂度上没有特殊含义。在这种情况下 n 和 N 只是用作同一个变量的不同值，如果他们给你 x.[=44 而不是 N 就没有区别=]
Important, when I use A => B, the => arrow means "A equals to B", or if you prefer "A ends up being B"
现在，考虑到原始的二次函数 T(n) = c*n^2
- 如果
N = 100和T(N) = 1ms那么他们告诉你T(100) = 1ms=>1ms = c * 100^2. - 你从前面的陈述中推断出的是
1ms = c * 100^2=>c = 1ms / 100^2. 现在只需将原公式
T(n) = cn2（即n = 5000）中的c和n替换为：T(5000) = (1/100^2) * 5000^2=>T(n) = 2.500ms=>T(n) = 2,5s