快速排序-空间复杂性-为什么是O(logN)而不是O(N)？

快速排序是一种常用的排序算法，它的空间复杂性为O(logN)而不是O(N)的原因是因为快速排序是一种原地排序算法，它不需要额外的空间来存储排序结果。

快速排序的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再按此方法对这两部分数据分别进行快速排序，整个过程递归进行，直到整个序列有序。

在快速排序的过程中，我们需要选择一个基准元素，将序列分割成两部分。具体的分割方法是通过不断地交换元素，将小于基准元素的放在左边，大于基准元素的放在右边。这样，每次分割都会将序列分成两部分，而不需要额外的空间来存储分割后的结果。

由于每次分割都会将序列分成两部分，而每一次分割都会将基准元素放在正确的位置上，所以在最坏情况下，快速排序的递归树的高度为logN。因此，快速排序的空间复杂性为O(logN)。

快速排序的优势在于它的平均时间复杂性为O(NlogN)，并且它是一种原地排序算法，不需要额外的空间来存储排序结果。它适用于大规模数据的排序，尤其是在内存有限的情况下。快速排序也被广泛应用于各种编程语言和开发场景中。

腾讯云提供了云服务器（CVM）和云数据库（CDB）等产品，可以满足快速排序算法的运行需求。您可以通过以下链接了解更多关于腾讯云产品的信息：

相关·内容

【漫画】为什么说O(n)复杂度的基数排序没有快速排序快？

这样的话，不是可以排的更快吗？ ? 老大：脑子反应的挺快啊。是的，是可以以最高位来排序的，而且也像你说的，以最高位来排序的话，是可以减少数据之间比较的次数。...1、基数排序是一种用空间换时间的排序算法，数据量越大，额外的空间就越大? 我的想法：我觉得基数排序并非是一种时间换空间的排序，也就是说，数据量越大，额外的空间并非就越大。...因为在把元素放进桶的时候，是完全可以用指针指向这个元素的，也就是说，只有初始的那些桶才算是额外的空间。 2、居然额外空间不是限制基数排序速度的原因，那为啥基数排序没有快速排序快呢？...基数的时间复杂度为O(n)，不过他是忽略了常数项，即实际排序时间为kn(其中k是常数项)，然而在实际排序的过程中，这个常数项k其实是很大的，这会很大程度影响实际的排序时间，而像快速排序虽然是nlogn，...需要说明的是，基数排序也并非比快速排序慢，这得看具体情况，（不要被标题所影响哈）。而且，数据量越大的话，基数排序会越有优势。 3、有人可能会问，说了这么多，那到底是基数排序快还是快速排序快呢？

7421 0

学习前端算法前你需要了解的‘大O表示法’

「空间复杂度：S(n)」空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。我们这里只讨论的是时间复杂度。...这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于...O（log n）,也叫对数时间，这样的算法包括二分查找 O(n)，线性时间，包括简单查找 O(n*log n)，包括快速排序（业界俗称快排），一种速度较快的快速排序 O（n^ x）,包括平方时间、立方时间...」排序法最差时间分析平均时间复杂度稳定度冒泡排序 O(n2) O(n2) 稳定快速排序 O(n2) O(n*log2n) 不稳定选择排序 O(n2) O(n2) 稳定二叉树排序 O(n2...) O(n*log2n) 不一定插入排序 O(n2) O(n2) 稳定堆排序 O(n*log2n) O(n*log2n) 不稳定希尔排序 O O 不稳定「参考文章」什么是算法？

7723 0

常见算法时间复杂度

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。 2、空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。...这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于...算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。...如快速排序的最坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。...在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。下面是一些常用的记法：访问数组中的元素是常数时间操作，或说O(1)操作。

5512 0

CC++工程师面试题（STL篇）

deque（双端队列）：在未排序状态下，查找时间复杂度为O(n)，类似于vector。但在有序状态下，可以利用二分查找，降低查找时间复杂度为O(log n)。...stack（栈）和queue（队列）：查找时间复杂度为O(n)，因为它们是容器适配器，提供了先进先出（FIFO）或后进先出（LIFO）的接口，并不支持快速查找操作。...deque 采取一块所谓的 map（不是 STL 的 map 容器）作为主控，这里所谓的 map 是一小块连续的内存空间，其中的每个元素（此处成为一个结点）都是一个指针，指向另一段连续的内存空间，称作缓冲区...缓冲区才是 deque的存储空间的主体。红黑树的特性，为什么要有红黑树红黑树是一种自平衡的二叉搜索树，它具有以下特性：节点颜色：每个节点要么是红色，要么是黑色。...O（logN），而unordered_map的时间复杂度是最好情况是O(1)，最坏情况是O（N）。

1650 0

Redis的ZSet底层数据结构，ZSet类型全面解析

但是查找其他元素时，就没有这么高效了，只能逐个查找下去，比如 entryN 的复杂度就是 O(N)ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请效率较低。...2.3.3 为什么需要跳表（WHY）/跳表高效的动态插入和删除因为普通链表查找一个元素时间复杂度O(n)；而跳表查找的时间复杂度为O(logn)，查找速度更快。...3.2 MySQL为什么用B+树，而不是跳表MySQL是持久化数据库、即存储到磁盘上，因此查询时要求更少磁盘 IO，且 Mysql 是读多写少的场景较多，显然 B+ 树更加适合Mysql。...，而Redis是内存中读取数据、不涉及IO，因此使用了跳表，跳表模型是更快更简单的方式3.3 ZSet为什么用跳表，而不是B+树/红黑树/二叉树1）ZSet为什么不用B+树，而用跳表时间复杂度优势：跳表是一种基于链表的数据结构...2）ZSet为什么不用红黑树、二叉树红黑树、二叉树查找一个元素的时间复杂度也是O(logn)ZSet有个核心操作，范围查找：跳表效率比红黑树高，跳表可以做到 logn 时间复杂度内，快速查找，找到区间起点

1231 0

究竟什么是时间复杂度，怎么求时间复杂度，看这一篇就够了

O(n^2) 同样的同理我们在看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^...2) 但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，我们这里说的O 代表的就是一般情况，不是严格的上界所以这里大家知道这么一回事就好了面试中面试官绝对不会针对快速排序的时间复杂度问题来讨论...i，直接说是logn，正式因为logij 是就一个常数所以，这样就应该不难理解了我们为什么忽略底数了如果时间复杂度是一个复杂的表达式，我们如何简化有时候，我们去计算时间复杂度的时候发现不是一个...（因为常数项并不会因为n的增大而增加计算机的操作次数） O(2*n^2 + 10*n) 去掉常数系数（我们刚刚已经详细讲过为什么可以去掉常数项的原因了） O(n^2 + n) 只保留保留最高项去掉数量级小一级的...O(m*n*logn)，那我们比较一下时间效率O(m*n*logn) 是不是比第一种方法O(m*n*n)更快一些呢很明显O(m*n*logn) 要优于O(m*n*n) 所以先把字符串集合排序在遍历一遍找到两个相同字符串的方式要比直接暴力枚举的方式更快

2.6K1 0

快速排序 Vs. 归并排序 Vs. 堆排序——谁才是最强的排序算法

知乎上有一个问题是这样的：堆排序是渐进最优的比较排序算法，达到了O(nlgn)这一下界，而快排有一定的可能性会产生最坏划分，时间复杂度可能为O(n^2)，那为什么快排在实际使用中通常优于堆排序？...首先先看一个排序算法图：排序方法平均情况最好情况最坏情况辅助空间稳定性冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定简单选择排序 O(n^2) O(n^2) O(n^2)...O(nlogn) O(nlogn) O(1) 不稳定归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定快速排序 O(nlogn) O(nlogn) O(n^2) O(logn...那么，为什么要说快速排序的平均情况是最快的呢？实际上在算法分析中，大O的作用是给出一个规模的下界，而不是增长数量的下界。...可能对于快速排序来说就是10，但因为是常数级所以不影响大O。

1.6K2 0

关于时间复杂度，你不知道的都在这里！

同样的同理再看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，「所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)」。...「但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界」。如图所示： ? 我们主要关心的还是一般情况下的数据形式。...去掉运行时间中的加法常数项（因为常数项并不会因为n的增大而增加计算机的操作次数）。 O(2*n^2 + 10*n) 去掉常数系数（上文中已经详细讲过为什么可以去掉常数项的原因）。...那看看这种算法的时间复杂度，快速排序时间复杂度为O(nlogn)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有m次的字符比较的操作，就是O(m * n * logn) 。...我们对O(m * n * logn + n * m) 进行简化操作，把m * n提取出来变成 O(m * n * (logn + 1))，再省略常数项最后的时间复杂度是 O(m * n * logn)。

1.3K4 0

算法复杂度O(1),O(n),O(logn),O(nlogn)的含义

相信很多开发的同伴们在研究算法、排序的时候经常会碰到O(1)，O(n)，O(logn)，O(nlogn)这些复杂度，看到这里就会有个疑惑，这个O(N)到底代表什么呢？带着好奇开始今天文章。...首先o(1), o(n), o(logn), o(nlogn)是用来表示对应算法的时间复杂度,这是算法的时间复杂度的表示。不仅仅用于表示时间复杂度，也用于表示空间复杂度。...其作用：时间复杂度是指执行这个算法所需要的计算工作量；空间复杂度是指执行这个算法所需要的内存空间；时间和空间都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少；...比如冒泡排序，就是典型的O(n x n)的算法，对n个数排序，需要扫描n x n次。...(n-1) 时间复杂度O(logn)—对数阶，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。

6.8K3 0

「时间管理」JavaScript算法时间、空间复杂度分析

T(n)：代码执行的时间 n：数据规模 f(n)：每行代码执行的次数总和 O：表示 T(n) 与 f(n) 成正比注意，初学者可能会认为这种方法就代表真实的代码执行时间，并不是这样，其代表的是代码的执行时间随数据规模增长的变化趋势...归并排序、快速排序、堆排序的时间复杂度都是 O(nlogn)。...O(1) O(n) O(n^2) 我们还是通过代码来逐个分析： O(1) const a = 1; let b = 2; 我们定义的变量a、b所占有的空间并不会随着某个变量的变化而变化，所以它的空间复杂度为...n 的增大而增大，所以它的空间复杂度就是 O(n)。...「如果初始化一个二维数组 n*n，那么它的空间复杂度就是 O(n^2)。」除此之外，O(logn)、O(nlogn) 这样的对数阶空间复杂度在平时也很少见，这里不再展开。

5733 0

「时间管理」JavaScript算法时间、空间复杂度分析

T(n)：代码执行的时间 n：数据规模 f(n)：每行代码执行的次数总和 O：表示 T(n) 与 f(n) 成正比注意，初学者可能会认为这种方法就代表真实的代码执行时间，并不是这样，其代表的是代码的执行时间随数据规模增长的变化趋势...归并排序、快速排序、堆排序的时间复杂度都是 O(nlogn)。...O(1) O(n) O(n^2) 我们还是通过代码来逐个分析： O(1) const a = 1; let b = 2; 我们定义的变量a、b所占有的空间并不会随着某个变量的变化而变化，所以它的空间复杂度为...会随着 n 的增大而增大，所以它的空间复杂度就是 O(n)。...「如果初始化一个二维数组 n*n，那么它的空间复杂度就是 O(n^2)。」除此之外，O(logn)、O(nlogn) 这样的对数阶空间复杂度在平时也很少见，这里不再展开。

3802 0

搞定大厂算法面试之leetcode精讲2.时间空间复杂度

插入排序的时间复杂度我们都说是O(n^2) ，但是插入排序的时间复杂度和输入数据有很大的关系，假如输入数据是完全有序的，则插入排序的时间复杂度是O(n)，假如输入的数据是完全倒序的，则时间复杂度是O(n...快速排序是O(nlogn)，快速排序的在最差的情况下时间复杂度是O(n^2) ，一般情况下是O(nlogn)，所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)，但是我们依然说快速排序的时间复杂度是...归并排序的时间复杂度是O(nlogn)，自顶而下的归并，从数据规模为n分割到1，时间复杂度是O(logn)，然后不断向上归并的时间复杂度是O(n)，总体时间复杂度是O(nlogn)。...)，所以最后的时间复杂度是O(n * slogs) + O(s * nlogn) = O(nslogs + nslogn) = O(ns * (logs+logn)) 空间复杂度空间复杂度指的是算法在运行过程中所占存储空间的大小...(n - 1); } //O(logn)，递归了logn层，递归栈空间是O(logn)的复杂度 var search = function (nums, target) { return search_interval

4493 0

常见排序算法代码实现及特性分析

希尔排序没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N^2)复杂度的算法快得多。...此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。...+(N-1) = N * (N-1) / 2，故时间复杂度为O(N^2)；（4）空间复杂度：O(1) 五、快速排序（重要） 1.基本思想：快速排序是对冒泡排序的一种改进，从待排序区间选择一个基准值（...O(logN)，快速排序的空间消耗主要是递归调用的地方。...，N / 2^k = 1，（层数）k = logN，进而得出 O(N) = N + 3 * N * logN = N*(logN)；（4）空间复杂度：O(N)，二路归并时需要开辟额外的数组空间来进行排序

7870 0

【数据结构】八大经典排序（两万字大总结）

O(N*logN)，所以堆排序的时间复杂度为：O(N*logN)；空间复杂度堆排序直接在原数组上进行建堆和选数操作，没有额外的内存消耗，空间复杂度为：O(1)；稳定性由于堆排序中相同的数据做父节点还是孩子节点...，空间复杂度为：O(1)；非递归版本的栈有额外空间消耗，空间复杂度为：O(logN)；稳定性由于快速排序选出的 key 值是不确定的，所以不稳定； 6.9 特性总结快速排序整体的综合性能和使用场景都是比较好的...，所以被称之为快速排序；时间复杂度：O(N*logN)；空间复杂度：O(1) – 递归，O(logN) – 非递归；稳定性：不稳定； ---- 7....排序总结排序方法平均情况最好情况最坏情况辅助空间稳定性直接插入排序 O(n²) O(n) O(n²) O(1) 稳定希尔排序 O(n*logn)~O(n²) O(n1.3) O(n²)...) O(n²) O(1) 稳定快速排序 O(n*logn) O(n*logn) O(n²) O(logn)~O(n) 不稳定归并排序 O(n*logn) O(n*logn) O(n*logn) O(

6180 0

算法之旅 | 快速排序法

今天跟大家分享多种排序算法里使用较广泛，速度快的排序算法 —— 快速排序法 [ 平均时间复杂度为O (n logn) ]。...快速排序法的原理快速排序是一种划分交换排序，它采用分治的策略，通常称其为分治法。分治法基本思想：将原问题分解为若干个规模更小但结构与原问题相似的子问题。...“基准”都是序列中最中间的一个数（是中位数，而不是位置上的中间），那么每次都把当前序列划分成了长度相等的两个子序列。...这时候，第一次就有n/2、n/2两个子序列，第二次就有n/4、n/4、n/4、n/4四个子序列，依此类推，n个数一共需要logn次才能排序完成（2^x=n，x=logn），然后每次都是n的复杂度，时间复杂度为...O（n logn）空间复杂度最坏情况：需要进行n‐1 次递归调用，其空间复杂度为 O（n）最好情况：需要logn次递归调用，其空间复杂度为O（logn）算法的稳定性快速排序是一种不稳定排序算法

8475 0

算法解析（挖坑法快速排序）

这意味着冒泡排序在处理大规模数据时可能会非常低效。相比之下，快速排序算法的空间复杂度为O(logn)至O(n)，而平均时间复杂度为O(nlogn)。...在算法分析中，O(n), O(n^2), O(logn), O(nlogn) 等是表示算法复杂度的大O表示法（Big O notation）。它描述了算法执行时间或所需空间随输入规模n增长的趋势。...平均情况（Average Case）：在平均情况下，即输入数据的分布是随机的，快速排序的性能仍然相当好。尽管算法形成的二叉树可能不是完全平衡的，但树的高度仍然保持在O(logn)范围内。...因此，最坏情况下的时间复杂度为O(n^2)。空间复杂度分析：快速排序的空间复杂度主要取决于递归调用栈的深度。在最优和平均情况下，递归树的高度为O(logn)，因此空间复杂度为O(logn)。...但在最坏情况下，递归树高度为O(n)，空间复杂度为O(n)。然而，需要注意的是，快速排序的空间复杂度并不包括存储输入数组本身的空间，因为这部分空间与算法本身的实现无关。

601 0

快速排序

1 背景我们都知道，算法是解决实际问题的步骤，是前人智慧的结晶。那么为什么会有快速排序呢？这就需要了解下传统排序算法的缺点。传统的排序算法有冒泡排序、选择排序和插入排序。...它们的共同点就是两两比较，算法的时间复杂度高达 O(n^2)，不适合大规模排序。我们接下来来看下时间复杂度仅为 O(nlogn) 的快速排序算法，它用到了分治思想，非常巧妙。...所以，快速排序不是一个稳定排序算法。...5.2 空间复杂度主要是递归造成的栈空间的使用。最好情况递归树深度为 logn，每次递归中只使用了常数的空间，空间复杂为 O(logn)。...最坏情况需要进行 n-1 次递归，每次递归中只使用了常数的空间，空间复杂度为 O(n)平均空间复杂度O(logn)

1542 0

面试中的 10 大排序算法总结

尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。...对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为： O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM...桶排序的最好效率能够达到O(N)。总结：桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。...如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。...从平均时间来看，快速排序是效率最高的，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后者相比较的结果是，在n较大时归并排序使用时间较少，但使用辅助空间较多。 2.

1.1K3 0

聊聊数据结构和算法

0 目录 1 为什么要懂数据结构和算法 2 什么是数据结构和算法 3 什么是时间复杂度分析 4 什么是空间复杂度分析 5 总结一般我们学习算法都是这样的经历: 是不是从学校开始，你就觉得数据结构难学...一般情况下把所有对数阶的时间复杂度都记为 O(logn)，对数之间是可以互相转换的，log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32...因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 了。...而且，O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。...常见的空间复杂度就是 O(1)、O(n)、O(n2 )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

3932 0

快速排序 QuickSort

简单讲每次一个小排序都会选出等于区,然后排小于区和大于区快排分两种经典快排比较基准为数组最后一个数随机快排比较基准为数组内随机一个数快排时间复杂度O(N*logN) 额外空间复杂度O(logN...O(N2)，平均的时间复杂度是O(N*lgN)。...这句话很好理解：假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢？至少lg(N+1)次，最多N次。 为什么最少是lg(N+1)次？...快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。...为什么最多是N次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

2213 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

快速排序-空间复杂性-为什么是O(logN)而不是O(N)？

相关·内容

【漫画】为什么说O(n)复杂度的基数排序没有快速排序快？

学习前端算法前你需要了解的‘大O表示法’

常见算法时间复杂度

CC++工程师面试题（STL篇）

Redis的ZSet底层数据结构，ZSet类型全面解析

究竟什么是时间复杂度，怎么求时间复杂度，看这一篇就够了

快速排序 Vs. 归并排序 Vs. 堆排序——谁才是最强的排序算法

关于时间复杂度，你不知道的都在这里！

算法复杂度O(1),O(n),O(logn),O(nlogn)的含义

「时间管理」JavaScript算法时间、空间复杂度分析

「时间管理」JavaScript算法时间、空间复杂度分析

搞定大厂算法面试之leetcode精讲2.时间空间复杂度

常见排序算法代码实现及特性分析

【数据结构】八大经典排序（两万字大总结）

算法之旅 | 快速排序法

算法解析（挖坑法快速排序）

快速排序

面试中的 10 大排序算法总结

聊聊数据结构和算法

快速排序 QuickSort

扫码

相关资讯

热门标签

活动推荐

运营活动

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐