算法O，有没有比O（n^2)低的方法？

来源：蜘蛛抓取(WebSpider) 时间：2019-09-07 18:28 标签： 算法O

再高的效率恐怕够呛除非所有數都分布在很小的一个区间里，或许有类似计数排序的方法

如果是基于比较排序的，排序的过程本身就可以用来记录逆序的个数，

因此各种排序算法O应该都可以用来统计逆序

我知道模可以用O(nlogn)实现，但是还有没有更高效的,或是别的算法O

>因此各种排序算法O应该都可以用來统计逆序。

所有用来统计逆序的方法都可用于排序这回方向对了么？

感觉有点蹊跷这是真的么？

>因此各种排序算法O应该都可以用来統计逆序
 规约方向反掉了。。

>感觉有点蹊跷这是真的么？ 

如果这个是对的那统计逆序才有nlogn的下界。用排序解逆序只能说明逆序的朂优算法O有nlogn的上界

原来是说效率上界的问题，碰到这种证明我一般都保持沉默

感觉排序是找逆序的前提，不过排序的同时也可以统计逆序！

>感觉有点蹊跷这是真的么？
 如果这个是对的那统计逆序才有nlogn的下界。用排序解逆序只能说明逆序的最优算法O有nlogn的上界

>不过排序的同时也可以统计逆序！ 

mergesort改一下就是nlogn的了，不过估计lz已经知道了

>感觉排序是找逆序的前提

这感觉做题还行，要是证明复杂度上下界的話一般都不管用

nlogn，这是分治策略里有这个的网站协同过滤时需要用到计算逆序数，用分治策略达到nlogn

真的有o(n)的吗，除非数据范围非常嘚小

匿名用户不能发表回复！

拍照搜题秒出答案，一键查看所有搜题记录

拍照搜题秒出答案，一键查看所有搜题记录

拍照搜题秒出答案，一键查看所有搜题记录

这是求时间复杂度,O不是函数或者公式

O(1): 表示算法O的运行时间为常量

O(n): 表示該算法O是线性算法O

O(n2): 对数组进行排序的各种简单算法O例如直接插入排序的算法O。

O(n3): 做两个n阶矩阵的乘法运算

O(2n): 求具有n个元素集合的所有子集的算法O

O(n!): 求具有N个元素的全排列的算法O

O(n?)表示当n很大的时候复杂度约等于Cn?，C是某个常数，简单说就是当n足够大的时候n的线性增长，复杂喥将沿平方增长

一个算法O执行所耗费的时间，从理论上是不能算出来的必须上机运行测试才能知道。但我们不可能也没有必要对每个算法O都上机测试只需知道哪个算法O花费的时间多，哪个算法O花费的时间少就可以了并且一个算法O花费的时间与算法O中语句的执行次数荿正比例，哪个算法O中语句执行次数多它花费时间就多。一个算法O中的语句执行次数称为语句频度或时间频度记为T(n)。

一般情况下算法O中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))

为算法O的渐进时间复杂度简称时间复杂度。

你对这个回答的评价是

我要回帖

更多关于 算法O 的文章

 

随机推荐