“Computers are incredibly fast, accurate, and stupid. Human beings are incredibly slow, inaccurate, and brilliant. Together they are powerful beyond imagination.”- Albert Einstein, physicist

什麼是演算法?

國中我們都學過函數，給定輸入後得到輸出，演算法也是一樣，可以把它想像成一個函數，我需要輸入資料，然後輸出答案。

假設我覺得明天下雨的機率跟今天下雨的機率有關係，而且明天下雨的機率會等於今天下雨的機率乘上2，那麼我可以寫一個函數：

f(x) = 2 * x

這就是一個演算法，他解決了預測明天下雨機率的問題，輸入是今天下雨的機率，輸出是明天下雨的機率。

電腦程式的本質上是一個演算法來告訴電腦的執行步驟。

為什麼需要演算法?

你可能聽過，很多公司在面試的時候都會考演算法，這是為什麼?

寫演算法就像是在寫數學題，主要是在鍛鍊你的邏輯思維，如果你的演算法強，那麼在學習其他東西時，上手的速度也會比其他人快一些。

(有說法是，公司可能多個部門都需要人才，一個最普遍的評判標準就是考演算法)

因此學習演算法對於奠基電腦科學這塊磚是很重要的！

演算法的分類

你可能聽過很多名詞：暴力法(Brute Force)、貪心法(Greedy)、動態規劃(Dynamic Programming)、Hash、Two Pointer、數論、圖論等等…。它們可能在時間跟空間的使用上會有所不同，但它們的本質都只是解決問題的方法。

怎麼開始學習演算法?

知行合一

寫程式也就是理性思考，我們要將主觀的感受轉換成客觀的認知。舉例來說：

主觀感受：我覺得今天好熱。

客觀認知：今天的氣溫是35度，正常人認為會熱的溫度是30度以上，所以今天很熱。

在學習演算法的初期，我們只需要培養寫程式的思維以及熟悉使用的程式語言，因此先以簡單易懂的題目做出發，先以實現為主，再去考慮到優化問題！

Note: 提醒一下：在看其他人的解答之前，建議是先想過一段時間，如果還是沒有想法的話，再看一下別人的解題思路會比較合適。如果沒有經歷過思考的環節而直接看解答的話，很容易讓自己的思維被其他人給帶著走。

如果是有想法，但不知道怎麼實現，有可能是你對你使用的程式語言不夠熟悉，可以多看別人是怎麼使用的！

首先就是要有提供題目的網站，考慮到開發環境以及題目難易度問題，這邊以最耳熟能詳的LeetCode 出發！

創建好帳號後，點進Problems後，可以看到，LeetCode提供非常豐富的資源以及功能，學習計畫、每日一題、答題記錄等等...，讓我們從第一題Two Sum開始！

Two Sum

題目描述：

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

題目需要我們找到這個Array中，哪兩個數的總和為Target，返回這兩個數的index。有時候看完題目後，你可能會想到一些奇怪的測資，這時候可以留意題目敘述以及下方的Constraints：

Constraints:

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• Only one valid answer exists.

點擊Run可以跑Test Case，確認Test Case沒問題後，可以點Submit，這時候會有更多測資對你的程式下毒手！

# Sol1 Brute Force (暴力法)
# 用雙層loop去遍歷每種組合 O(n^2)
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range (0, len(nums)):
            for j in range (i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return i, j
# Sol2
# 使用一個Dict(map)的數據結構去紀錄已經出現過的數，只需要一次遍歷 O(n)
class Solution:
    def twoSum(self, nums, target):
        _map = {}
        for i in range(0, len(nums)):
            if target - nums[i] in _map:
                return [_map[target - nums[i]], i]
            _map[nums[i]] = i
        return []
        
# Sol2 運用語言特性簡化
class Solution:
    def twoSum(self, nums, target):
        _map = {}
        for i, num in enumerate(nums):
            if target - num in _map:
                return [_map[target - num], i]
            _map[num] = i
        return []

提交通過後，會顯示你的Runtime和Memory的使用量，

當你提交了Sol1和Sol2後，可以看到Sol2比Sol1快很多，這就帶到演算法的一個重點：
同一個問題可以有很多種不同的解法，每種解法所花費的時間不同，我們的首要目標就是要讓我們的程式跑得越快越好！

因此誕生了許多數據結構和不同的演算法出現，就算是時間複雜度相同的演算法，在面對不同測資的情況下仍會有不同的表現，因此需要依照當前使用場景所會遇到的測資去選擇合適的演算法！

(Note: Memory相對於Runtime較為不重要是因為如今硬體的發展，Memory相較於以前比較不那麼吃緊，普遍會以速度作為優先考量(用空間換取時間)，但在硬體資源較受限的情況下，就會比較有影響。)