算法复杂度分析

将时间复杂度记为O(n)

针对代码逐行从上到下计算即可，因为常数 c 可以取任意大小，所以操作数量中的各种系数、常数都可以忽略。

1. 忽略与 n 无关的操作。因为是常数项对时间复杂度不产生影响。
2. 省略所有系数。 n 前面系数对时间复杂度没有影响，2n、n + 10 都可以简化记为 n 次。
3. 循环嵌套时使用乘法。 总操作数量等于内外层循环操作数量之积，每一层循环依然可以使用 1 、 2 技巧。

go
copy code
func algorithm(n int) {
    a := 1
    a = a + n
    for i := 0; i < 5 * n + 1; i++ {
        fmt.Println(0)
    }
    for i := 0; i < 2 * n; i++ {
        for j :=0; j < n + 1; j++ {
            fmt.Println(0)
        }
    }
}

T(n) = n^2^ + n

时间复杂度由 T(n) 中最高阶来决定。 这是因为 n 趋于无穷大时，最高阶将发挥主导作用，其他项都可以省略。

例如：

设输入数据大小为 n ，则常见的时间复杂度类型包括（从低到高）。

O(1) < O(log n) < O(n) < O(n log n) < O(n^2^) < O(2^n^) < O(n!)

master 公式 $$ T(N) = a * T(N/b) + O(N^d) $$

• a：函数内递归函数数量
• b：每次递归分解数量
• d：除去递归外的时间复杂度

则有

$$ log_ba > d \qquad 复杂度(O(N^{log_ba}) $$

$$ log_ba = d \qquad 复杂度O(N^{d *logN}) $$

$$ log_ba < d \qquad 复杂度O(N^d) $$

go
copy code
package main

import (
	"fmt"
	"math"
)

func main() {
	arr := []int{7, 4, 8, 4, 2, 66, 43, 45, 4, 44, 2, 6}
	max := process(arr, 0, len(arr)-1)
	fmt.Println(max)
}

func process(arr []int, l, r int) int {
	if l == r {
		return arr[l]
	}

	mid := l + ((r - l) >> 1)
	leftMax := process(arr, l, mid)
	rightMax := process(arr, mid+1, r)
	return int(math.Max(float64(leftMax), float64(rightMax)))
}

这个例子里面 d=0 除去递归外其他复杂度都是常数阶；a=2每个函数内又有两个递归函数；b=2 每次都将原数组二分。

所以

$$ ∵ \ log_22=1; \ d = 0; \ 1 > 0; \ log_ba > d \qquad 复杂度(O(N^{log_ba}) \ ∴ \ 复杂度为O(N^{log_ba}) = O(N^{log_22}) = O(N) $$

go
copy code
package main

import "fmt"

func main() {
	arr := []int{1, 4, 2, 6, 7, 3, 2, 4}
	process(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

func process(arr []int, l, r int) {
	if l == r {
		return
	}

	middle := l + ((r - l) >> 1)
	process(arr, l, middle)
	process(arr, middle+1, r)
	merge(arr, l, middle, r)
}

func merge(arr []int, l, m, r int) {
	help := make([]int, r-l+1, r-l+1)
    // 当前 help 数组下标
	i := 0
    // 左数组起始下标
	p1 := l
    // 右数组起始下标
	p2 := m + 1

    
    // 判断左右两个数组哪个值小就首先复制哪个值进去
    // 左右两个数组下标哪个先越界就退出去
	for p1 <= m && p2 <= r {
		if arr[p1] <= arr[p2] {
			help[i] = arr[p1]
			p1++
		} else {
			help[i] = arr[p2]
			p2++
		}
		i++
	}

    // 将剩下数值复制进辅助数组里
    // 两个循环只会命中一个，将未越界的数组剩下数都复制进去
	for p1 <= m {
		help[i] = arr[p1]
		i++
		p1++
	}
	for p2 <= r {
		help[i] = arr[p2]
		i++
		p2++
	}

    // 上面排序从 l 下标开始，此处复制也从 l 开始
	for i, num := range help {
		arr[l+i] = num
	}
}

这个例子里面 d=1 除去递归外还需要遍历一遍数组；a=2每个函数内又有两个递归函数；b=2 每次都将原数组二分。

所以

$$ ∵ \ log_22=1; \ d = 1; \ 1 = 1; \ log_ba = d \qquad 复杂度O(N^{d *logN}); \ ∴ \ 复杂度为O(N^{d * logN}) = O(N^{1 * logN}) = O(NlogN) $$

$$ ∵ \ log_22=1; \ $$