2 u010949779 u010949779 于 2013.09.14 20:20 提问

快速排序的时间复杂度O(nlogn)

谁可以解释下O(nlogn) 是什么意思吗。。我知道n是需要循环的次数。logn呢。?

2个回答

phoenixylf
phoenixylf   2013.09.16 10:25
已采纳

logn是指用到了二分查找。即每次取之前总数的一半。直到最后一个就是我们要找的。
数学解释:假设原来总的个数为N个,每次查找为上一次的一半,经过x次找到我们要的结果。
公式表达:N*(1/2)^x=1;(x为指数)
解:x=log2(N)=logN(简写);
数学的计算相信你没问题的。

tlxzsz
tlxzsz   2014.02.27 17:44

logn是数学运算符,表示以2为底n的对数。
logn是指用到了二分查找。即每次取之前总数的一半。直到最后一个就是我们要找的。
数学解释:假设原来总的个数为N个,每次查找为上一次的一半,经过x次找到我们要的结果。
公式表达:N*(1/2)^x=1;(x为指数)
解:x=log2(N)=logN(简写);
数学的计算相信你没问题的。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
快速排序[平均时间复杂度O(NlogN)]
基本思想: 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这10个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便,就让第一个数6作为基准数。分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换它们,用两个变量i和j分别指向最左边和最右边,直到i=j,将基准数与a[i]交换,再继续递归
快速排序算法的时间复杂度为什么是O(NlogN),还有O(N^2)
转载自:http://www.cnblogs.com/pugang/archive/2012/07/02/2573075.html 经常听人谈起各种排序算法的时间复杂度,这个是O(n2)的,那个是O(n)的,这些人讲起来可谓滔滔不绝,但是你停下来问问他为什么这个是这个复杂度,他是怎么算出来的?往往没几个人能说出来。这个是一个浮躁的社会,大家都追求速度,到处复制,粘贴代码,拿人家的代码跑一
关于快速排序和插入排序最坏时间复杂度为O(nlogn)的算法
1.快速排序:根据T(n) = T(ðn) + O(n) (0 因此关键问题是怎样解决划分标准的问题, 因此产生下列线性时间找中位数的算法:将数组a有n个元素, 划分成5个一组, 则共有[n/5]个元素, 对于每组用一般的排序找中位数,需要25次, 则总共需要O(25*[n/5]) = O(n), 然后在这些中位数中递归找其中位数需要T(n/5)次,然后以找到的中位数x来作为划分标准则显然
基于递归策略的排序算法
1-3     解析 :注意是归并的躺数的数量级而不是归并排序的时间复杂度, 因此为logN。 1-1 对N个不同的数据采用冒泡排序进行从大到小的排序,当元素基本有序时交换元素次数肯定最多。 (1分) T         F 作者: DS课程组 单位: 浙江大学 1-2 对N个记录进行快速排序,在最坏的情况下,其时间复杂度
Java-时间复杂度为O(nlogn)的排序算法(快速排序, 归并排序, 堆排序, 希尔排序)
/** 包含多种静态排序方法 * Created by Andre on 2016/6/27. */ public class Sorter { /** * 快速排序 * 递归形式 * 第一个记录为枢轴 * 不稳定 * @param a 需要排序的数组 * @param low 数组的起始下标 * @param h
堆排序(Heap Sort)
堆排序 Heap Sort   堆排序是一种选择排序,其时间复杂度为O(nlogn)。 堆的定义   n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。   情形1:ki 2i 且ki 2i+1 (最小化堆或小顶堆)   情形2:ki >= k2i 且ki >= k2i+1 (最大化堆或大顶堆)   其中i=1,2,…,n/2向下取整;
排序的最低时间复杂度为什么是O(nlogn)
这个首先要明确一点,只用到比较的排序算法最低时间复杂度是O(nlogn),而像桶排这样的只需要O(R)(R为桶的大小) 为了证明只用到比较的排序算法最低时间复杂度是O(nlogn),首先要引入决策树。 首先决策树是一颗二叉树,每个节点表示元素之间一组可能的排序,它予以京进行的比较相一致,比较的结果是树的边。 先来说明一些二叉树的性质,令T是深度为d的二叉树,则T最多有2^片树叶。 具有L片
快速排序时间复杂度为O(n×log(n))的证明
之前只知道快速排序的平均时间复杂度为O(n×log(n)),最糟糕时复杂度为
每天一道LeetCode-----链表排序,要求复杂度在O(nlogn)
原题链接Sort List要求在O(nlogn)的时间复杂度下排序链表,且时间复杂度在O(1)涉及到O(logn)的算法有 二分法 快速排序 归并排序 二分法通常应用在已排序的序列中,且常用语查找算法,而不用作排序算法快速排序需要从两边向中间逼近,对待链表而言同样不现实归并排序类似于二分,不断切分已有序列再合并成一个有序序列,排序操作集中在合并过程中且通常是将两个有序序列合并成一个综上,归并排序是适
快速排序的时间复杂度nlogn是如何推导的??
本文以快速排序为例,推导了快排的时间复杂度nlogn是如何得来的,其它算法与其类似。 对数据Data = { x1, x2... xn }: T(n)是QuickSort(n)消耗的时间; P(n)是Partition(n)消耗的时间; (注:Partition专指把n个数据分为大小2份的时间)