快速排序时间复杂度
快速排序时间复杂度如下:
排序算法的时间复杂度是若文件的初始状态是正序的,一趟扫描即可完成排序。
比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,是不会再交换的。
各种常用的算法,对时间复杂度的情况是这样。直接插入排序,是n平方的时间复杂度。直接选择排序是n平方的时间复杂度,冒泡排序也是n平方的时间复杂度。快速排序,希尔排序,和归并排序,都是n×(logn)的时间复杂度。
扩展资料:
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同,但时间复杂度相同,都为O(n^2)。
次线性时间
对于一个算法,若其匹配T(n) = o(n),则其时间复杂度为次线性时间(sub-linear time或sublinear time)。实际上除了匹配以上定义的算法,其他一些算法也拥有次线性时间的时间复杂度。例如有O(n)葛罗佛搜索算法。