时间戳

首页 > 解决方案 > 这种快速排序实现的空间复杂度

python - 这种快速排序实现的空间复杂度

问题描述

这个问题很笼统，但也有问题：

def quick_sort(lst):
    if len(lst) < 2: return lst
    pivot_lst = lst[0]
    left_side = [el for el in lst[1:] if el < pivot_lst]
    right_side = [el for el in lst[1:] if el >= pivot_lst]
    return quick_sort(left_side) + [pivot_lst] + quick_sort(right_side)

时间复杂度：O(nlog(n))预期，O(n^2)最坏情况

空间复杂度：？？？

因此，对于预期的时间复杂度，最好的情况是何时left和right均分，以下系列将适用于 n 大小的输入：

n + n/2 + n/4 + n/8 +...  +1 
= n(1 + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + ... . )
= O(n)

It follows that in the worst case, which occurs when the pivot point selected is the largest or smallest value in the list, this would apply:

n + (n-1) + (n-2) +... + 1
= (n^2 + n) / 2 
= O(n^2)

我的问题是，上面的系列是否分别代表 和 的预期和最差空间复杂O(n)性O(n^2)？

我正在为堆栈帧内存如何在这里发挥作用而苦苦挣扎。我们只是添加它吗？

所以，如果它O(log(n))，那么空间复杂度是O(n) + O(log(n)) -> O(n)

或者它与辅助数据的关系是什么？

我是否可以得出结论，当辅助数据结构和递归堆栈都存在时，我们只需要计算两者中的较大者吗？

标签： pythonalgorithmbig-ospace-complexity

解决方案

概括

在这个快速排序的实现中，是的——预期的辅助空间复杂度是O(n)，最坏情况下的辅助空间复杂度是O(n^2)。

我正在为堆栈帧内存如何在这里发挥作用而苦苦挣扎。我们只是添加它吗？

所以，如果它的 O(log(n))，那么空间复杂度是 O(n) + O(log(n)) -> O(n)

[...]

我是否可以得出结论，当辅助数据结构和递归堆栈都存在时，我们只需要计算两者中的较大者吗？

不。

我认为您正确地注意到递归堆栈深度在O(log(n))预期的情况下，但错误地认为这意味着它的空间复杂度也在O(log(n))预期的情况下。这不一定是真的。

  • 一个单独的堆栈帧可以表示比 更多的空间O(1)。
  • 一帧代表多少空间可能因帧而异。

因此，在求算法的总空间复杂度时，不能将其递归深度与其数据需求分开分析，然后在最后将两者相加。你需要一起分析它们。

一般来说，您需要了解：

  • 递归的深度——会有多少堆栈帧。
  • 对于这些堆栈帧中的每一个，它的空间复杂度是多少。这包括函数参数、局部变量等。

然后，您可以将同时处于活动状态的所有堆栈帧的空间复杂度相加。

示例：预期案例

想象一下这个函数调用树n=8。我使用该符号表示“使用元素quick_sort(n)列表进行快速排序”。n

quick_sort(8)
    quick_sort(4)
        quick_sort(2)
            quick_sort(1)
            quick_sort(1)
        quick_sort(2)
            quick_sort(1)
            quick_sort(1)
    quick_sort(4)
        quick_sort(2)
            quick_sort(1)
            quick_sort(1)
        quick_sort(2)
            quick_sort(1)
            quick_sort(1)

由于您的实现是单线程的，因此一次只有一个分支处于活动状态。在最深处，它看起来像：

quick_sort(8)
    quick_sort(4)
        quick_sort(2)
            quick_sort(1)

或者，一般来说：

quick_sort(n)
    quick_sort(n/2)
        quick_sort(n/4)
            ...
                quick_sort(1)

让我们看看每一帧会占用多少空间。

<calling function>
    lst: O(n)
    
    quick_sort(n)
        lst: O(1)
        pivot_lst: O(1)
        left_side: O(n/2)
        right_side: O(n/2)
        
        quick_sort(n/2)
            lst: O(1)
            pivot_lst: O(1)
            left_side: O(n/4)
            right_side: O(n/4)
            
            quick_sort(n/4)
                lst: O(1)
                pivot_lst: O(1)
                left_side: O(n/8)
                right_side: O(n/8)
                
                ...
                    quick_sort(1)
                        lst: O(1)

请注意，我正在考虑lst始终具有空间复杂度的参数O(1)来反映 Python 列表是按引用传递的。如果我们把它做成O(n),O(n/2)等等，我们就会重复计算它，因为它实际上和调用函数的left_sideor是同一个对象right_side。这最终不会影响此特定算法的最终结果，但通常您需要牢记这一点。

我在符号上也很草率。写作O(n/2)让人很想立即将其简化为O(n). 不要那样做：如果你这样做，你最终会夸大总空间复杂度。

简化一点：

<calling function>
    lst: O(n)

    quick_sort(n)
        everything: O(n/2)

        quick_sort(n/2)
            everything: O(n/4)

            quick_sort(n/4)
                everything: O(n/8)

                ...
                    quick_sort(1)
                        everything: O(1)

把它们加起来：

O(n) + O(n/2) + O(n/4) + O(n/8) + ... + O(1)
= O(n)

示例：最坏情况

使用与上述相同的方法，但为简洁起见跳过了一些步骤：

<calling function>
    lst: O(n)

    quick_sort(n)
        everything: O(n-1)

        quick_sort(n-1)
            everything: O(n-2)

            quick_sort(n-2)
                everything: O(n-3)

                ...
                    quick_sort(1)
                        everything: O(1)

O(n) + O(n-1) + O(n-2) + O(n-3) + ... + O(1)
= O(n^2)

推荐阅读