时间复杂度：是一个函数，它描述了算法的运行时间，并且给出了运行时间与输入规模之间的关系。

输入规模：一个问题的输入规模是保存输入数据所需要的bit位数

Time complexity measures the time that an algorithm takes as a function of the length in bits of its input

如 O(n), 其中n表示数据的输入规模

当我们处理一些图论、链表、数组、树等问题时，这个标准定义下的多项式时间和我们传统的多项式时间相差无几。

然而，当我们处理一些与数论有关的问题时，事情就不太乐观了。

如判断一个数是否是素数，输入数number，则number需要log number 个二进制位来存储，令k=log number

假如number为8， 则k为3。当k增加1变成4之后，则number变成了16,

即，根据定义，时间复杂度的输入规模是k，而不是number。这样求素数的时间复杂度为2^k，即O(2^n)

01背包问题，设背包大小为w，有n个物品。

用dp解时间复杂度似是O(w*n)。然而w也有上面的例子的问题，实际上时间复杂度是:O(n*2^logw)

上面两个例子的时间复杂度都是伪多项式时间(pseudo-polynomial)

参考文章：

https://blog.csdn.net/zhan723284893/article/details/45014633

https://en.wikipedia.org/wiki/Time_complexity

https://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete

重温时间复杂度

原文：https://www.cnblogs.com/liangwenhan/p/11924766.html