分析算法

发表于 | 分类于

关注的是计算时间

分析算法的结果意味着预测算法需要的资源。虽然有时我们主要关心像内存、通信宽带或计算机硬件这类资源，但通常我们想度量的是计算时间。

最坏情况和最好情况

往往集中于只求最坏情况的运行时间，即对规模为n的任何输入，算法的最长运行时间

  • 最坏的运行时间确定了一个上界，这可以确保算法绝对不会需要比这更长的运行时间

  • 对于某些算法，最坏的情况经常出现

  • “平均情况”往往与最坏大致一样差

增长量级


我们只考虑公式中最重要的项（如 an^2）,因为当n的值很大时，低阶相对来说不太重要。我们也忽略最重要的项的常数项，因为对大的输入，在确定计算效率时常量银子不如增长率重要。

练习题

θ记号

θ(n^3) - θ(n^2) - 100n 忽略低阶项则为 θ(n^3)

选择排序

1
2
3
4
5
6
for i <- 1 to length[A]-1  
    do min <- i  
        for j <- i+1 to length[A]  
            do if A[j] < A[min]  
                then min <-j  
        exchange(A[i], A[min])

使用TypeScript实现选择算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class SelectSort {
    private sortArray: Array<number>

    public constructor(arr: Array<number>) {
        this.sortArray = arr
        this.selectSort()
    }

    private selectSort(): void {
        let len: number = this.sortArray.length

        for (let i: number = 0; i < len; i++) {
            let min: number = this.sortArray[i]
            let temp: number
            let index: number
            for (let j = i + 1; j < len; j++) {
                if (this.sortArray[j] < min) {
                    min = this.sortArray[j]
                    index = j
                }
            }
            temp = this.sortArray[i]
            this.sortArray[i] = min
            this.sortArray[index] = temp
        }
    }

    public printSortWell() {
        console.log(this.sortArray.toString())
    }

}

let selectSort: SelectSort = new SelectSort([3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48])
selectSort.printSortWell()

选择排序时间复杂度

选择排序的时间复杂度是O(N2)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1！因此，选择排序的时间复杂度是O(N2)

线性查找

再次考虑线性查找问题，在平均情况下，需要检查输入序列中的多少个元素？假定待查找的元素是数组中任何一个元素的可能性相等，在最坏情况下又怎样呢？用O形式表示，线性查找最坏情况运行时间是多少？并说明

  • 平均情况下需要查找序列中(1+n)/2个元素

  • 最坏情况下：n个元素。即O(n)为最坏

修改算法以获取最佳运行时间

应如何修改任何一个算法，才能使之具有较好的最佳情况运行时间

根据算法的最佳情况改变输入数据的分布（比如说顺序），使之符合最佳情况条件，这样就能拥有最佳运行时间。

总之是制造出符合最佳情况的条件