復(fù)雜度的計算方法遵循以下幾個原則

1. 首先，復(fù)雜度與具體的常系數(shù)無關(guān)，例如 O(n) 和 O(2n) 表示的是同樣的復(fù)雜度。我們詳細分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是說，一段 O(n) 復(fù)雜度的代碼只是先后執(zhí)行兩遍 O(n)，其復(fù)雜度是一致的。
2. 其次，多項式級的復(fù)雜度相加的時候，選擇高者作為結(jié)果，例如 O(n2)+O(n) 和 O(n2) 表示的是同樣的復(fù)雜度。具體分析一下就是，O(n2)+O(n) = O(n2+n)。隨著 n 越來越大，二階多項式的變化率是要比一階多項式更大的。因此，只需要通過更大變化率的二階多項式來表征復(fù)雜度就可以了。

值得一提的是，O(1) 也是表示一個特殊復(fù)雜度，含義為某個任務(wù)通過有限可數(shù)的資源即可完成。此處有限可數(shù)的具體意義是，與輸入數(shù)據(jù)量 n 無關(guān)。

總結(jié)

1. 一個順序結(jié)構(gòu)的代碼，時間復(fù)雜度是 O(1)。
2. 二分查找，或者更通用地說是采用分而治之的二分策略，時間復(fù)雜度都是 O(logn)。這個我們會在后續(xù)課程講到。
3. 一個簡單的 for 循環(huán)，時間復(fù)雜度是 O(n)。
4. 兩個順序執(zhí)行的 for 循環(huán)，時間復(fù)雜度是 O(n)+O(n)=O(2n)，其實也是 O(n)。
5. 兩個嵌套的 for 循環(huán)，時間復(fù)雜度是 O(n2)。

package main

import "fmt"

// 倒序排列 算法1
// 時間復(fù)雜度 O(n)+O(n) = O(n)
// 空間復(fù)雜度 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
// 時間復(fù)雜度 O(n/2) = O(n)
// 空間復(fù)雜度 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)
}

// 求最大值
// 時間復(fù)雜度 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)
}

// 查找出現(xiàn)次數(shù)最多的那個數(shù)字
// 時間復(fù)雜度 O(n2)
func testMaxCountValue(a []int) {
    //a := []int{ 1, 3, 4, 3, 4, 1, 3 }

    maxCountVal := -1
    timesMax := 0 // 全局最大次數(shù)
    timesTmp := 0 // 當(dāng)前元素次數(shù)
    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)
}