Day19 Analysis of Algorithms(Ⅰ)

●There may exist various algorithms for the same problem.
●We then compare these algorithms by measuring their efficiency.
●To do so, we estimate the growth rate of running time in function of input size n.
●We proceed to introduce the notion of time complexity.
●Similar to time complexity(时间复杂度), we later turn to the notion of space complexity(空间复杂度).
EX:Sum

第一行时间加总是2
第二行时间加总是n+1
第三行时间加总是2n
第四行时间加总是n
总共是4n+3
Big-O Notation
Big-o定义: f (n) ∈ O(g(n)) as n →∞
若有一个常数 c > 0 还有一些n0,那麽 f (n) ≤ c ×g(n) ∀n ≥ n0.
快速判断时间复杂度的方法:
1.Keep the leading term only.留着首项
2.Drop the coefficient.首项常数拿掉
3. time complexity.即为时间复杂度
EX:1. 8n^2 −3n + 4. ∈ O(n^2) 2.4n+3∈ O(n)
有一个k层回圈的规则,当有一个k层回圈则时间复杂度为O(n^k)。