算法时间复杂度的表示法O(n²)、O(n)、O(1)、O(nlogn)等是什么意思?

算法时间复杂度的表示法O(n²)、O(n)、O(1)、O(nlogn)等是什么意思?

大O函数指的是算法所耗时与输入规模之间的关系。不同的排序算法复杂度不一定相同。比如O(n^2)代表这个算法排序n个数,所耗CPU时间与n的平方在同一个数量级。
空间复杂度则是指空间与问题规模的关系。
算法时空复杂度是衡量一个算法优劣的主要因素。
简单说O(n²)表示当n很大的时候,复杂度约等于Cn²,C是某个常数,简单说就是当n足够大的时候,n的线性增长,复杂度将沿平方增长。

O(n)也是差不多的意思,也就是说n很大的时候复杂度约等于Cn,C是某个常数。

发表回复

您的电子邮箱地址不会被公开。