Day.2 什麽是时间、空间复杂度?

时间复杂度（Time complexity)

我们要怎麽知道一个程序要跑多久?
正常来说要真的执行下去才精准知道，那有没有事前可以预估的方式？
有的，一般来说我们可以透过观察执行次数，去估算时间复杂度。

看一下这段程序

func sum(nums []int) int {
    sum := 0 // 执行一次
    for _, num := range nums {
        sum += num // 执行n次 (视nums的长度)
    }

    return sum // 执行一次
}

上面这一段程序，我们可以说时间复杂度为O(2+n)，但一般会把执行没几次的去掉，只把影响最大的n留下来，试想看看如果n是一百万，那个2几乎不影响时间。以这个case来说，最终可以改为O(n)。(时间复杂度常用大O符号表述)

再看看这段程序

func mappingItem(users []*User, items []*Item) {
    for _, user := range users {
        for _, item := range items {
            if user.ID == item.OwnerID {
                user.Item = item
                break
            }
        }
    }
}

直觉上你看到两个回圈，可能你会回答O(n^2)，但要注意两个input的长度可能是不一样，所以应该以O(m*n)来表示。那如果是同一个array，然後回圈两次，这就是O(n^2)。

还有一些比较常见的

1. O(log n) 对数
2. O(1) 常数
3. O(2n) 指数

时间复杂度的推算其实满数学的，这边就不深究了，先简单给个概念，如果之後有遇到会再说。

来看一下这张图

注：图源(https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6)

O(n)跟O(n^2)大家把n代入10000就可以看到很巨大的差异了，更不要说O(n^3)，当n的数字变大了可能会面临timeout的情况。

O(n)是线性时间(linear)，成本是合理的，随着input愈大，时间等比的成长。
写程序尽量追求O(n)或更好的解法

空间复杂度（Space complexity)

func hashmap(nums []int) {
    hash := map[int]bool{}
    for _, n := range nums {
        hash[n] = true
    }

    fmt.Println(hash)
}

这时候我们可以说空间复杂度为O(n)，因为多了一个变数hash来记nums的资料，随着input的资料愈大，记忆体用量会愈多。如果不会随着input而增加记忆体用量，则空间复杂度为O(1)。

明天来讲一下时间跟空间的取舍～