Question

数据结构中时间复杂度中的“数量级”这个名词是什么意思

数据结构中时间复杂度中的“数量级”这个名词是什么意思

Answer 1

就是说，相对的运行时间倍数。
如果是o(1)，那就是说在固定时间内完成，如果是o(n)，那么n越大，当然就越久，所以它和o(1)就不在一个数据级，相应的o(n平方)就更久了，对吧
这个感觉就和1、10、100、10000这种数量级是一样的。

Answer 2

数量级释义：
用来量度或估计某些物理量大小的一种概念。当一个物理量的数值写成以10为底的指数表达式时，指数的数目就是这个物理量的数量级。例如地球赤道半径为6378千米，可以写成6.378×10^3千米或6.378×10^6米。就千米来说，它的数量级是3；就米来说，它的数量级是6。

Answer 3

O(n)表示时间复杂度。
按数量级递增排列，常见的时间复杂度有：
常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)......
在n不断增大情况下，数量级越大，O(n)就增长得越快，通常数量级所使用的比例为10，那么1000和100的数量级分别为3和2，当然也可以用2作为比例，4和16的数量级分别为2和4。
类比到时间复杂度，当n很大的时候，O(2^n)和O(n)之间差的数量级就非常巨大。