1. 问题的下界(Lower Bounds)

• 即任何一种算法解决一个问题所必须的最小运行时间
• 假设一个问题的下界为F(n),而当前解决该问题的最好的算法为A，其最坏情形时间复杂度为W(n),如果F(n)=W(n)则A是最优的算法。
• 排序问题的计算时间下界为，计算时间复杂度为的排序算法是最优算法。
• 堆排序算法是最优算法
• 快速排序算法是最优算法

  2. 找最大元素

Find Max(A)
    max =2
    for j = 2 to n do
        if A[j] > max then
        max = A[j]
    return max

• 下界为n-1
• 最坏情形的时间复杂度为n-1

  3. 总结