分治法合并排序和快速排序时间复杂度推导

### 分治法中的时间复杂度推导

#### 快速排序的时间复杂度推导过程

快速排序是一种基于分治策略的高效排序算法。其基本思想是通过一次划分操作将待排序序列分割成两部分，使得左边的部分都小于右边的部分，然后再分别对这两部分继续进行同样的处理。

对于长度为 \( n \) 的数组，在最坏情况下每次选取的基准都是当前无序区的最大或最小元素，则需要做 \( O(n) \) 次比较才能找到该基准的位置；而最好的情况则是平均分配左右区间，此时只需大约一半次数即 \( O(\log{n}) \)[^1]。因此：

- **最好情况下的时间复杂度**：当数据均匀分布时，每轮分区都能大致平分成两个相等大小的小问题，递归树的高度约为 \( \log_{2}{n} \)，每一层涉及的操作量级均为线性的 \( O(n) \)，所以整体性能达到最优状态——\( T(n)=O(n\cdot{\log}_{2}{n}) \)

- **最差情况下的时间复杂度**：如果输入的数据已经有序或者逆序排列，那么每一次都会退化到极端不平衡的状态，形成一条长长的链表结构，这时高度变成了 \( n \)，从而导致整个运算效率下降至平方级别——\( T(n)=O({n^{2}}) \)

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr)//2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left)+middle+quicksort(right)

#### 归并排序的时间复杂度推导过程

归并排序同样是利用了分治的思想来实现高效的排序功能。它的工作原理是从中间位置切分原始列表直到只剩下一个单独项为止，之后再逐步向上回溯组合已排好序的小片段最终得到完整的有序集合。

由于每次都将原数列一分为二直至单个元素构成的新子集，故此构建出的一棵完全二叉树具有固定的层次数目等于 \( {\log}_{{2}}{n}\ ) 。而在每一个节点处所做的工作仅仅是简单的合并相邻两项而已，这一步骤所需时间为常数阶 \( O(1)\ ),但是考虑到要遍历整棵树的所有结点完成全部配对任务，实际消耗还是呈现线性增长趋势— — 即 \( O(n) \ ).综上所述:

\[T(n)=O(n\cdot{\log}_{2}{n})\]

def merge_sort(lst):
    if len(lst)<=1:
        return lst
    
    mid=len(lst)//2
    left=merge_sort(lst[:mid])
    right=merge_sort(lst[mid:])
    
    merged=[]
    while left and right:
        if left[0]<=right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    merged.extend(left or right)
    return merged