TWICE出新MV啦!

轉載於:JYP Entertainment 官方YouTube

非本科生直接查wiki，Big Ｏ是什麼意思，根本就是個錯誤。
我再重讀一次大學也還是看不懂那些運算符號，因為根本不想懂XD

Big Ｏ notation(Big 歐)

最簡單的認知，用來估算演算法效益的符號，估算程式(演算法)解決問題的效益。
常常在leetcode上的一些題目或大神解說中，我是Ｏ(n)或Ｏ(log n)解法，等於是說這些解法的效益如何，但用更直接一點的說法是，這個解法或演算法，最差狀況下要跑幾次才有解答。

上一篇猜數字的例子中，假設有n筆資料，最差狀況下需要跑n次才會有解答，所以這個解法效益評估就是O(n)。
而二元搜索法是以2為底求100(資料數)的對數，所以是Ｏ(log n)。

Ｏ(n):線性時間。
Ｏ(log n):對數時間。

緊急補充，log 2是殺毀??
如果跟我一樣數學不好，無法去記對數與指數，那請記得log是對數。

指數

 2 ** n = 8
 n = 3 # n為指數。

對數

log 2 8 = n
 n = 3 # n為 以2為底8的對數。

像二元法就是log2，面對100個資料要執行幾次，如昨天的答案是7次。所以其實評估演算法的效益是以次數來評估，另外資料的增加也可由對數發現，資料越多，所需解決的次數是正比但不是等比。

Ｏ(n)是最慢的嗎?

不是耶，很多狀況下，如果資料有10個，可以最多跑10次就算到解答，那有時也是很厲害。
判斷與加減乘除等，這些跑一次就算一次，很多解法遠遠是超過Ｏ(n)狀況的。

以這題舉例。leetcode 344. Reverse String

def reverse_string(s)
  s.reverse!
end

p reverse_string(["h","e","l","l","o"]) #=> ["o","l","l","e","h"]

先忘記reverse的真正原理，無論是設定一個新的空陣列，將資料pop一個一個放進新陣列。

arr = []
s.size time do
  arr << s.pop
end 
# 這個解法leetcode上錯喔，這是在s外處理。

還是

left = 0
right = s.length - 1
    
while left < right do
  s[left], s[right] = s[right], s[left]
  left += 1
  right -= 1
end

都屬於Ｏ(n)，相信也很難找出更快的了，所以初學演算法不是去要求自己能更快解決問題，而是去了解哪些問題有更好的解法，因為很多演算法到後面會變成。
Ｏ(n*log n) : 本身資料數乘上對數。
Ｏ(n**2) : 資料數的2次方(一樣資料越多越恐怖)。
Ｏ(n!) : 降冪乘法，宇宙無敵恐怖那種。

改天解題能清楚知道自己絕對是Ｏ(n)就能解出，說不定就是一種成就?
另外，還是reverse一次解決最愉悅呀!