algorithm - 讲座幻灯片说明 : Computable in Polynomial Time

Question

我 = 输入

|I| = 输入数

A(I) = P(I) 表示算法A 在输入I< 上给出问题P 所需的输出/strong>.

为什么Time(A, I) <= |I|^2 不适用于小的I？

Answer 1

来自 wiki :

...Since this function is generally difficult to compute exactly, and the running time is usually not critical for small input, one focuses commonly on the behavior of the complexity when the input size increases, that is on the asymptotic behavior of the complexity.

幻灯片中的措辞可能有点误导，并不是说它不适用，而是更准确地说:它可能不适用于小输入。