時間複雜度（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)。

明天來講一下時間跟空間的取捨～