山东大学算法导论期末考试重点

### 山东大学《算法导论》期末考试重点内容概要

#### 一、基本概念与分析方法
理解并掌握算法复杂度的概念及其表示方式，包括时间复杂度和空间复杂度。能够熟练运用渐近记号O, Ω 和Θ来描述函数的增长速度[^1]。

#### 二、经典排序算法
深入学习各种内部排序算法的工作原理及性能特点，比如快速排序、堆排序以及归并排序等。对于每种排序方法都需要清楚其平均情况下的时间和空间开销，并能解释为什么某些情况下特定类型的排序更优。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i=j=k=0
        
        while i<len(L) and j<len(R):
            if L[i]<R[j]:
                arr[k]=L[i]
                i+=1
            else:
                arr[k]=R[j]
                j+=1
            k+=1
            
        while i<len(L):
            arr[k]=L[i]
            i+=1
            k+=1
                
        while j<len(R):
            arr[k]=R[j]
            j+=1
            k+=1

#### 三、图结构上的优化问题求解
熟悉最短路径计算（Dijkstra算法）、最小生成树构建(Prim/Kruskal)，还需注意这些算法适用条件的不同之处；另外关于网络流最大流量等问题也需有所涉猎。

#### 四、动态规划与贪心策略的应用场景区分
两者都是解决多阶段决策过程的有效手段之一，在实际应用中如何判断一个问题更适合采用哪种思路至关重要。例如背包问题是典型的DP案例而Huffman编码则是基于贪婪法则实现最优前缀码表的设计。