Algorithm

用户8279

2025年12月16日修改

Basic

Worst Case Analysis

对于一个二分查找问题，假设有一个长度为n的有序数组，假设T(n)是最坏情况下的查找时间。​

每次比较可以看作常数操作O(1)，比较中间值后就会递归到左半部分或者右半部分，因此​

T(n)=T(n/2)+O(1)

对于这个递推公式，有边界条件T(1)=O(1)

T(n)=T(n/2)+O(1)=T(n/4)+O(1)+O(1)=T(n/2^k)+k*O(1)

令2^k=n, k=logn，所以T(n)=T(1)+logn*O(1)=O(logn)

Merge Sort

Divide and conquer

Divide: 将数组分成左右两个部分，递归的进行排序

Merge:

common.docs_name - LarkCCM_Docs_Menu_Image

对于左右两个数组，如果A[p]<=A[q]，则将A[p]加入C；如果A[q]<A[p]，则将A[q]加入C。当p=n/2，则将右数组的剩余部分A[q...n-1]加入C；如果q=n，则将左数组的剩余部分A[p...n/2-1]加入C。​

Worst Case Analysis

Merge过程需要O(n)，所以

T(n)=2T(n/2)+O(n)

Boundary condition: T(1)=O(1) 只有一个元素时不需要排序

令k=logn，那么

Quick Sort

选出一个pivot，左数组为比pivot小的部分，右数组为比pivot大的部分，对左右数组分别做排序，返回时无需额外的merge操作。以下是Quick Sort原地实现​

代码块

def quick_sort(arr, low, high)：​
    if low < high:​
        pivot_index = partition(arr, low, high)​
        quick_sort(arr, low, pivot_index)​
        quick_sort(arr, pivot_index+1, high)​
        ​
def partition(arr, low, high):​
    pivot = arr[high]​
    i = low - 1​
    for j in range(low, high):​
        if arr[j] <= pivot:​
            i += 1​
            arr[i], arr[j] = arr[j], arr[i]   # 把小的值换到i位置​
    arr[i+1], arr[high] = arr[high], arr[i+1] # i永远指向一个小于等于pivot的值​
    return i+1​
​

Worst Case Analysis

虽然没有merge的过程了，但是在divide之前需要进行partition，partition仍然需要O(n)操作，因此​

T(n)=2T(n/2)+O(n)

T(n)=O(nlogn)

Heap Sort

Min Heap (Tree)的性质：Min heap一定是complete binary tree (n nodes深度为logn)，Minimum被存储在root，每个node的值都小于children​

•
Delete是将树的末尾的值copy到root，然后一路向下shift down重新形成Min heap，时间是O(logn) (树的最大深度)​

•
Insert是在树的末尾添加一个node，然后一路向上shift up重新形成Min heap，时间是O(logn)​

删除3和插入4:

50%

Algorithm​

Algorithm