初識算法之美
本篇是學習了《趣學算法（第2版）》 第一章之後總結的。
對算法的理解：
計算機雖然可以高效的進行運算，但是有很多問題拼的不是算力，而是策略。如果沒有策略的去計算，那再強的運算能力也只能稱為「蠻力」。策略就是幫助我們如何用更少的計算步驟、更快的速度去運算出結果。換言之，策略就是你設計算法的思路，目的只有一個就是：快人一步。
計算機不同於人腦，人腦面對問題可以先去「觀察」、「分析」，然後把複雜轉化成簡單問題（跟數學題一樣，算法就是簡便的解題思路）。目前在絕大多數領域計算機還不具備這個功能，離開了人腦，計算機還只是一個人的使用工具罷了。
算法有兩個衡量標準：
- 時間長短（時間複雜度）
- 佔用內存大小（空間複雜度）
先展望一下學習歷程：
算法學習是一個循序漸進的過程，經常訓練解題能力，逐步積累解題方法策略，最後內化成自己的知識，靈活運用去應對新的問題。
「初極狹，才通人。復行數十步，豁然開朗。」，挺喜歡這句話😁
算法知識點
-
高斯算法（倒序相加）
-
數列求和
算法題目
求： $S_n = 1 + 2 + 2^2 + 2^3 + … + 2^{63}=$
該函數屬於爆炸增量函數。
做題思路
方法一
公式法
如果還記得高中數學知識，不難發現，這是一個等比數列求和問題，$a_1 = 1，公比q = 2，n = 64$
等比數列求和公式：$$S_n = a_1 * \frac{1 – q^n}{1 – q} ，(q ≠ 1)$$
本文暫不講解公式推導過程
代入公式，上面的式子 = $1 * \frac{1 – 2^{64}}{1 – 2} = 2^{64} – 1 = 18446744073709551615$ ，從而轉化問題，解題
方法二
忘記方法叫什麼名字了，主要原理就是銷項，使問題轉化成第一項和最後一項的差。
根據原式，等號兩邊同時乘以2，得式子②$2S_n = 2 + 2^2 + 2^3 + … + 2^{63} + 2^{64}$
用式子② – 原式 = $S_n = 2^{64} – 1 =18446744073709551615$
據專家統計，每顆麥粒的平均重量約41.9毫克，這些麥粒的總重量為：
$18446744073709551615×41.9$
$=772918576688430212668.5(毫克)$
$≈7729000（億千克）$
全世界人口按77億計算，每人差不多可以分得100000千克（即100噸）！
總結
常見的算法時間複雜度有以下幾類。
-
常數階。
常數階算法的運行次數是一個常數，如5、20、100。常數階算法的時間複雜度通常用O(1)表示。 -
多項式階。
很多算法的時間複雜度是多項式，通常用 0(n)、$O(n2)$、$0(n3)$等表示。 -
指數階。
指數階算法的運行效率極差，程序員往往像躲「惡魔」一樣避開這種算法。指數階算法的時間複雜度通常用$O(2n)$、$O(n!)$、$O(nn)$等表示。 -
對數階。
對數階算法的運行效率較高，通常用$O(logn)$、$O(nlogn)$等表示。
指數階增量隨着的增加而急劇增加，而對數階增長緩慢。它們之間的關係如下：
$$O(1)＜O(logn)＜O(n)＜O(nlogn)＜O(n2)＜O(n3)＜O(2n)O(n!)＜O(nn)$$
在設計算法時，我們要注意算法複雜度增量的問題，盡量避免爆炸級增量。
通過上面一個算法小例子，又勾起了我對數學的興趣。算法跟數學是息息相關的，平常也要複習一下數學知識，相信也會有所幫助的。
我是 甜點cc
熱愛前端，也喜歡專研各種跟本職工作關係不大的技術，技術、產品興趣廣泛且濃厚，等待着一個創業機會。本號主要致力於分享個人經驗總結，希望可以給一小部分人一些微小幫助。
希望能和大家一起努力營造一個良好的學習氛圍，為了個人和家庭、為了我國的互聯網物聯網技術、數字化轉型、數字經濟發展做一點點貢獻。數風流人物還看中國、看今朝、看你我。
