搜搜考试网c++请问O(nlogn), O(1)分别指什么 我知道O(n)指线性
来源：学生作业帮 编辑：搜搜考试网作业帮 分类：综合作业 时间：2024/07/15 20:07:21
c++请问O(nlogn), O(1)分别指什么 我知道O(n)指线性
这是算法的时空复杂度的表示.不仅仅用于表示时间复杂度,也用于表示空间复杂度.
O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系.其中的n代表输入数据的量.
比如时间复杂度为O(n),就代表数据量增大几倍,耗时也增大几倍.比如常见的遍历算法.
再比如时间复杂度O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度.比如冒泡排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n×n次.
再比如O(logn),当数据增大n倍时,耗时增大logn倍（这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度）.二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标.
O(nlogn)同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍.这个复杂度高于线性低于平方.归并排序就是O(nlogn)的时间复杂度.
O(1)就是最低的时空复杂度了,也就是耗时/耗空间与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变.哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标（不考虑冲突的话）
再问： 非常感谢你的详细回答，我还有一个问题，比如给你一个function T(n)=2n+3n+3 让你找到它的big O notation running time, 是不是这样就可以了? T(n)=2n+3n+3->T(n)=5n+3->linear->O(n)
O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系.其中的n代表输入数据的量.
比如时间复杂度为O(n),就代表数据量增大几倍,耗时也增大几倍.比如常见的遍历算法.
再比如时间复杂度O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度.比如冒泡排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n×n次.
再比如O(logn),当数据增大n倍时,耗时增大logn倍（这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度）.二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标.
O(nlogn)同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍.这个复杂度高于线性低于平方.归并排序就是O(nlogn)的时间复杂度.
O(1)就是最低的时空复杂度了,也就是耗时/耗空间与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变.哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标（不考虑冲突的话）
再问： 非常感谢你的详细回答，我还有一个问题，比如给你一个function T(n)=2n+3n+3 让你找到它的big O notation running time, 是不是这样就可以了? T(n)=2n+3n+3->T(n)=5n+3->linear->O(n)