时间、空间复杂度和Big O

分析时间和空间复杂度的重要性

• 提高算法效率，用最少的资源，达到最高的效率
• 选择正确的数据结构和算法

Big O

• 用户描述算法的时间和空间复杂度，特指最坏的情况
• 给定输入长度N，特指最坏的情况，算法花费的时间和空间上限
• 描述了算法和输入大小的关系

空间复杂度

• 算法需要的内存大小和输入N之间的关系
• 建立大小为n的一维数组，需要内存为O(n),二维数组需要内存为O(n²)

Big O计算方法

• 除去常量
• 除去非主要因子
• 例子:

O(N+8)= O(N)
O(N²+N) = O(N²)

例题

斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。

func fib(N int) int {
    if N <= 0 {
        return 0
    }
    if N == 1 {
        return 1
    }
    return fib(N-1)+fib(N-2)
}

• 时间复杂度
  递归树节点个数-时间复杂度上限
  O(2⁰+2¹+2²+...+2^n-1-1) =O(2ⁿ-1)
  如果递归方程有M个递归call,时间复杂度大概率是O(Mⁿ)
• 空间复杂度
  O(n)*每一层操作占用空间

搜素插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

解法-利用二分法:

func searchInsert(nums []int, target int) int {
    if len(nums) == 0{
        return 0
    }
    start := 0
    high := len(nums)-1
    for start <= high {
        mid := (start+high)/2
        num := nums[mid]
        if target == num{
            return mid
        }else if(target > num) {
            start = mid + 1
        } else {
            high = mid-1
        }
    }
    return start
}

• 时间复杂度
  二分次数时间复杂度取决于二的多少次方等于N，时间复杂度O(logN)

常用算法时间复杂度

• 从低到高：O(1),O(logN),O(NlogN),O(N²) (E:边，V:节点)

算法	时间复杂度	空间复杂度
深度优先遍历	O(|E|+|V|)	O(|V|)
广度优先遍历	O(|E|+|V|)	O(|V|)
快速排序	O(N2)	O(N)
归并排序	O(NlogN)	O(N)
冒泡排序	O(N2)	O(1)
插入排序	O(N2)	O(1)