什么是算法?

人生皆算法，算法的本質，是解決問題的方法，遇到問題，尋找答案，解決問題，是作為一個人，一生都在做的事情。

算法是人類思維的產物，是解決問題的方案，并且，它能夠映射到計算機世界去實現，完成一些人類不擅長的事情，比如大量重復的計算。

算法很有魅力，它很特別，但是并不神秘，我們時時刻刻都在運用著算法背后的“解決問題”的思想去生活，去過著每一天。

用計算機思維去思考問題

算法是普通的，也是特別的，它是人類使用計算機思維思考的產物，能夠讓人類更加充分地利用計算機這個人類發明的工具，這也是信息時代特有的產物。

既然是計算機思維，當然有其特點：
概念不重要，理解即可，不必記憶，不必急于掌握，直接看實例體會。

“玩具”問題

計數：判斷一個byte（無符號整數）里面有多少個bit的值是1

算法一

很簡單的想法，將十進制數轉換為一位一位的二進制，然后看看是不是1就好了，就是簡單的數數。

// method 1 int cal_1(unsigned char number) {unsigned char count = 0;while (number != 0){int div = number % 2;if (div == 1) {count++;}number /= 2;}return count; }

算法二

上面是我們解決問題的第一種想法。

下面我們加一種假設，假如內存空間足夠大，且使用函數次數足夠多，我們是不是可以提高算法的效率？

要知道，1字節大小的無符號整數，一共2⁸ = 256種，如果我們連續10000次調用函數，每一次都使用除二取余法（算法1），就大量重復計算了，這個時候不妨提前算好把結果存起來，然后直接訪問結果（就像緩存、cache那樣的思想）。

也就是所謂的打表查表

// 計數：判斷一個byte（無符號整數）里面有多少個bit的值是1 #include <iostream> using namespace std;int num_table[256] = { 0 };// method 1 int cal_1(unsigned char number) {unsigned char count = 0;while (number != 0){int div = number % 2;if (div == 1) {count++;}number /= 2;}return count; }// method 2 int cal_2(unsigned char number) {return num_table[number]; }int main(){// 存儲答案for (unsigned char i = 0; i < 255; i++) {num_table[(int)i] = cal_1(i);}// 直接訪問cout << cal_2(15);return 0; }

我們開始使用算法1，存儲了一張表，之后再需要使用的時候，就能夠直接查表得結果，而不需要再重復計算了，如果調用100000萬次，效率將會比算法1顯著提高。

當然……由于數據量對計算機來說太小了還是，測試不出很大的差異其實。

如果規模更大，會有顯著效果。

算法三

對于算法一

• 省空間，因為沒占用多少數據段
  對于算法二
• 省時間，因為提前儲存好了答案，只需要訪問數組就可以

對于前面兩種算法，是根據不同需求不同情況取使用的，但是涉及到了算法設計考慮的兩個維度：時間和空間。

算法一省空間，費時間，算法二省時間廢空間，那么能不能兼得？

其實這種

不走極端取中間的兼得思想

在計算機中經常需要用到。

我們需要既省時間又省空間的算法。

與cache類似的設計思想

我們可以使用哈希表，采取如下策略

• 如果表中有值，那就直接取
• 如果沒有，就去計算，并且存表中

這樣一來，做到了拿走需要的，保存需要的，同時考慮了時間和空間兩方面的因素。

我們使用unordered_map完成這件事：

// 計數：判斷一個byte（無符號整數）里面有多少個bit的值是1 #include <iostream> #include <unordered_map> using namespace std;typedef std::unordered_map<unsigned char, int> result_map;// method three int cal_3(unsigned char number, result_map &map) {result_map::iterator count = map.find(number);if (count != map.end()) // 在無序映射表中{cout << "在表中 ";return count->second;}else // 不在表中{cout << "不在表中 ";int result = cal_1(number);map.insert(result_map::value_type(number,result)); // 插入鍵值對return result;}}int main(){result_map map;cout << cal_3(15, map) << endl; // 不在表中 4cout << cal_3(15, map) << endl; // 在表中 4cout << cal_3(10, map) << endl; // 不在表中 2cout << cal_3(10, map) << endl; // 在表中 2return 0; }

這樣，通過無序映射表，我們就完成了既節省時間，又節省空間的目的。

小結

我們來回顧一下。

對于這個問題

我們看到了問題，理解了問題

拆解問題，變成自己熟悉的

解決問題，創建解決問題的過程方案

設計解決流程，將其代碼實現

根據實際情況，優化解決方案

綜合考慮算法的時間和空間兩個維度的指標

我們通過這個超級簡單的例子，初步了解了算法的基本情況，我們繼續往下進行。

連續子序列和

讓我們體會一下不同的算法，不同的解決方案，感受一下它們之間的時間和空間上的性能差異。

一件事情，往往都是很多種解決方案，并且都能到達彼岸，但是過程不一樣，走過的路不同，花的時間也不同，算法的時空性能也是一樣的。

充分體會： 計算機世界是人類世界的二進制映射，與人類生活息息相關。

算法1：三層循環

取某個首位置i

取i后的某個位置j

計算[i,j]數值的和，與最大值比較，更新最大值

這是一種最樸素的思想了，我們看圖。
因此，我們需要

for(int i = 0; i < char_size; i++){for(int j = i; j < char_size; j++){1. 求和2. 更新maxValue} }

代碼如下：

#include <iostream> #include <vector> using namespace std;int max_subsequence_sum(const vector<int> &a) {int max_sum = 0;for (int i = 0; i < a.size(); i++) {for (int j = i; j < a.size(); j++) {int current_sum = 0;for (int k = i; k <= j; k++)current_sum += a[k];if (current_sum > max_sum)max_sum = current_sum;}}return max_sum; }int main() {vector<int> a = { 1,3,-1,2 };cout << max_subsequence_sum(a);return 0; }

但是，毫無疑問，三重循環，時間消耗過多了，我們得看看能不能優化。
將三重循環轉換為遞歸。

代碼暫不寫

算法2：兩層循環

算法3：一層循環

算法4：遞歸

算法比較

小結

之所以沒有談及后面的代碼，因為對于初學者來說比較復雜，看看就行了，充分體會的是同一個問題，達成同一個目的的情況下，不同算法的差異巨大，這也是算法魅力所在。

致謝

感謝北交大算法MOOC！

總結

以上是生活随笔為你收集整理的【算法】学习笔记（0）：算法初探（逻辑抽象 + 示例 + 代码实现）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。