time-complexity - 时间复杂度上的大写 N 与小写 n

Question

我遇到了以下问题，这让我很困惑:

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在时间复杂度上有什么区别？

Answer 1

大写字母N与小写字母n在时间复杂度上没有特殊含义。在这种情况下 n 和 N 只是用作同一变量的不同值，如果他们给你的不是 N ，那也没有什么区别x.

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

1. 如果 N = 100 和 T(N) = 1ms 那么他们告诉你 T(100)
= 1ms => 1ms = c * 100^2.
2. 你从前面的陈述中推导出的是 1ms = c * 100^2 =>c = 1ms/100^2。

3. 现在只需替换​​ T(n) = 的原始公式中的 c 和 ncn2(n = 5000):

   T(5000) = (1/100^2) * 5000^2 => T(n) = 2.500ms => T( n) = 2,5s