数据结构和算法学习笔记--复杂度：如何衡量程序运行的效率

复杂度的计算方法遵循以下几个原则

1. 首先，复杂度与具体的常系数无关，例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n)，其复杂度是一致的。
2. 其次，多项式级的复杂度相加的时候，选择高者作为结果，例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n 越来越大，二阶多项式的变化率是要比一阶多项式更大的。因此，只需要通过更大变化率的二阶多项式来表征复杂度就可以了。

值得一提的是，O(1) 也是表示一个特殊复杂度，含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是，与输入数据量 n 无关。

总结

1. 一个顺序结构的代码，时间复杂度是 O(1)。
2. 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)。这个我们会在后续课程讲到。
3. 一个简单的 for 循环，时间复杂度是 O(n)。
4. 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)。
5. 两个嵌套的 for 循环，时间复杂度是 O(n²)。

package main

import "fmt"

// 倒序排列 算法1
// 时间复杂度 O(n)+O(n) = O(n)
// 空间复杂度 O(n)
func testReverse1(a []int) {
    //a := []int{1, 2, 3, 4, 5}
    dataLen := len(a)
    b := make([]int, dataLen)

    for i := 0; i < dataLen; i++ {
        b[i] = a[i]
    }

    for i := 0; i < dataLen; i++ {
        b[dataLen-i-1] = a[i]
    }

    fmt.Println(b)
}

// 倒序排列 算法2
// 时间复杂度 O(n/2) = O(n)
// 空间复杂度 O(1)
func testReverse2(a []int) {
    //a := []int{1, 2, 3, 4, 5}

    tmp := 0
    dataLen := len(a)
    for i := 0; i < dataLen/2; i++ {
        tmp = a[i]
        a[i] = a[dataLen-i-1]
        a[dataLen-i-1] = tmp
    }

    fmt.Println(a)
}

// 求最大值
// 时间复杂度 O(n)
func testMaxValue(a []int) {
    //a := []int{1, 4, 3}

    maxVal := -1
    for i := 0; i < len(a); i++ {
        if a[i] > maxVal {
            maxVal = a[i]
        }
    }

    fmt.Printf("max value is %d \n", maxVal)
}

// 查找出现次数最多的那个数字
// 时间复杂度 O(n²)
func testMaxCountValue(a []int) {
    //a := []int{ 1, 3, 4, 3, 4, 1, 3 }

    maxCountVal := -1
    timesMax := 0 // 全局最大次数
    timesTmp := 0 // 当前元素次数
    for i := 0; i < len(a); i++ {
        timesTmp = 0
        for j := 0; j < len(a); j++ {
            if a[i] == a[j] {
                timesTmp += 1
            }
            //if timesTmp > timesMax {
            //  timesMax = timesTmp
            //  maxCountVal = a[i]
            //}
        }
        if timesTmp > timesMax {
            timesMax = timesTmp
            maxCountVal = a[i]
        }
    }

    fmt.Printf("max count value is %d \n", maxCountVal)
}

func main() {
    a := []int{1, 2, 3, 4, 5, 6}
    testReverse1(a)
    testReverse2(a)

    b := []int{1, 4, 3, 9}
    testMaxValue(b)

    c := []int{1, 3, 4, 3, 4, 1, 3}
    testMaxCountValue(c)
}