演算法與資結：解題時的測試與BCR

解題流程的細節與相關注意事項裡，我選了這兩個概念，因覺得較需要整理。

1. 解題時的測試：如果希望不要花一堆時間才能測試出bug，以下做法：
    a. 做「概念性測試」：也就是用眼睛去看、檢視、分析每行code，找找或想想「程式跑的，和我心裡想的，是不是一樣？」。

    b. 看看「看起來怪怪的程式」：e.g. x = length - 2，這種通常都是「易出錯」的地方。要找出來為何這樣寫。
 
    c. 看看「熱點（也就是你的經驗告訴自己容易出錯的東西）」：e.g. 遞迴的終止條件、二元樹的空節點、iterate linked list的起點和終點等等。

    d. 做小測試：e.g. 用較少元素的陣列，去發現相同的bug，會較快找到bug。

    e. 檢查「特殊情況」：像是空或單元素值、極端情形，或其他特殊情形要測。


順帶一提，很多人一聽到「設計演算法」就感到怕怕的。其實當想到如何解決時，可以「手動」做做看，通常我們的直覺會產生不錯的演算法。

e.g. 當我們想將班上的考試卷，找出Adam的分數時。很多人會直接掃迴圈。但如果日常生活中，我們直覺會先依A、B、C到Z先分類，之後到A中去找Adam的分數。
=> 等於我們想到用「雜湊桶」方式取代掃冗長loop的演算法。
=> 等於從思考自己如何解決的，將自己做法做個反向工程。
=>只是要注意大腦會做出的最佳化：如果我們知道班上沒有Z開頭名字的同學，則不用管這分類。因而演算法中要注意有這個辦法。


2. 理解「最理想執行時間（BCR: Best Conceivable Runtime）」，對解題很有幫助：
    a. 定義：一個問題能夠得到最好的執行時間。
                e.g. 如果要A、B陣列輸出所有值的配對，不會比O(n的平方)的執行時間更好了，因共有n的平方個配對要輸出。

    b. 不要和「最佳情況執行時間」搞混：兩者完全無相關。
        BCR是用於「問題且主要為輸入與輸出，和特定演算法無關」；
        最佳情況執行時間用於「特定演算法，且通常沒什麼價值」，我覺得可以用特例的角度去想最佳情況執行時間就會較易懂了。
 
    c. 最大價值：BCR不一定能達成，它只是表示解題的執行時間不能比它更好了。

    d. 對解題有用原因：

• 可用執行時間作為必須減少哪部分的提示：

               e.g. 想從A陣列去找出和B陣列中有交集的數字：因需至少檢查每個元素一次，需O(2n)，簡化為O(n)，所以BCR是O(n)。
                     => 但找的過程是含搜尋的，所以加總後現況是O(n的平方)，而這也是可以減少的部分，如將O(n)的搜尋降為O(log n)。
                     => 如此加總可以得到O(n log n)。

• 小於或等於BCR的工作都是「免費」的，因不會影響執行時間：

               e.g. 承上例，想將搜尋時間由O(log n)降至O(1)，可以做「預先計算」，也就是將B陣列的元素全丟到雜湊桶，而這需花的時間是O(n)。之後就可以直接查雜湊桶找到交集元素。
                    => 可知我們預先計算是O(n)，等於BCR的Ｏ(n)。這時算一下總執行時間：B陣列全部元素丟雜湊桶是O(n) + 對A陣列每個元素O(n) * 一個個檢查或搜尋是O(1) = 最後總執行時間仍為O(n)。註：因O(2n)簡化為O(n)。

• BCR告訴我們執行時間已最佳化，不要再做下去了。接下來應改善的是「空間複雜度」：

               e.g. 承上例，如果題目前提是「有序」的陣列，如此有機會去掉雜湊桶，減少額外空間，又能在O(n)中解決問題。

• 如果已達成BCR且具有O(1)額外空間。我們知道已不能再做任何最佳化Big O時間或空間。可以停止了。

    e. 注意：

• BCR不是「真正」的演算法概念，所以演算法教科書不會教。但在現實中解題很有效。
• 如果還不能掌握判斷題目的BCR，一定要先「搞定Big O時間」（如連結：https://lucrelin.blogspot.com/2019/04/big-o.html），這樣之後就能一秒內看出BCR。