Ruby、演算法学习心得(二) Big O notation。

TWICE出新MV啦!

非本科生直接查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次。所以其实评估演算法的效益是以次数来评估，另外资料的增加也可由对数发现，资料越多，所需解决的次数是正比但不是等比。

不是耶，很多状况下，如果资料有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一次解决最愉悦呀!~~