演算法複雜度

你好！今天的講座與其他講座略有不同。它的不同之處在於它僅與 Java 間接相關。 然而，這個主題對於每個程式設計師來說都非常重要。我們將討論演算法。什麼是演算法？簡單來說，這是為了達到預期結果而必須執行的一系列操作。我們在日常生活中經常使用演算法。例如，每天早上您都會面臨一項任務：去學校或上班，同時：

• 著裝
• 乾淨的
• 餵得很好

什麼演算法可以讓你達到這個結果？

1. 被鬧鐘叫醒。
2. 洗澡，洗臉。
3. 準備早餐，煮咖啡/茶。
4. 吃。
5. 如果您從晚上開始就沒有熨燙衣服，請熨燙它們。
6. 穿上衣服。
7. 離開這房子。

這一系列的操作肯定會讓你得到想要的結果。在程式設計中，我們工作的全部意義就是不斷解決問題。這些任務的很大一部分可以使用已知的演算法來執行。例如，您面臨一個任務：對陣列中 100 個姓名的清單進行排序。這個任務非常簡單，但可以透過不同的方式來解決。這是一種解決方案： 按字母順序對名稱進行排序的演算法：

1. 網路上購買或下載《俄羅斯人名詞典》1966 年版。
2. 在這本字典中找出我們清單中的每個名字。
3. 在一張紙上寫下這個名字位於字典的哪一頁。
4. 使用一張紙上的筆記將姓名按順序排列。

這樣一連串的行動能讓我們解決自己的問題嗎？是的，它將完全允許。這個解決方案會有效嗎？幾乎不。這裡我們討論演算法的另一個非常重要的屬性──它們的效率。該問題可以透過不同的方式解決。但無論是在程式設計或日常生活中，我們都會選擇最有效的方法。如果您的任務是製作黃油三明治，那麼您當然可以從播種小麥和擠奶開始。但這將是一個無效的解決方案——它將花費大量時間並花費大量金錢。為了解決你的簡單問題，你只需購買麵包和黃油。而小麥和牛的演算法雖然可以讓你解決問題，但太複雜了，無法應用在實務上。為了評估程式設計中演算法的複雜性，創建了一種稱為Big-O（“big O”）的特殊符號。 Big-O 可讓您估計演算法的執行時間在多大程度上取決於傳入演算法的資料。讓我們來看一個最簡單的例子—資料傳輸。想像一下，您需要以檔案的形式遠距離（例如5000公里）傳輸一些資訊。哪種演算法最有效？這取決於他必須處理的數據。例如，我們有一個 10 MB 大小的音訊檔案。 在這種情況下，最有效的演算法是透過互聯網傳輸檔案。只需幾分鐘！那麼，我們再次語音一下我們的演算法： “如果需要在5000公里的距離上以文件的形式傳輸信息，就需要使用互聯網上的數據傳輸。” 偉大的。現在我們來分析一下。 它能解決我們的問題嗎？總的來說，是的，它完全解決了這個問題。但對於它的複雜性你能說些什麼呢？嗯，現在事情變得有趣了。事實上，我們的演算法很大程度上取決於傳入的數據，即檔案的大小。現在我們有 10 MB，一切都很好。如果我們需要傳輸500兆位元組怎麼辦？20GB？500TB？30PB？我們的演算法會停止運作嗎？不，所有這些數據量仍然可以傳輸。 會需要更長的時間才能完成嗎？是的，它會的！現在我們知道了我們演算法的一個重要特徵：要傳輸的資料量越大，演算法完成所需的時間就越長。但我們想更準確地了解這種關係是什麼樣的（資料大小和傳輸資料所需的時間之間）。在我們的例子中，演算法的複雜度將是線性的。「線性」是指隨著資料量的增加，傳輸時間將大致成比例增加。如果資料量增加 2 倍，則傳輸時間將增加 2 倍。如果資料量增加10倍，傳輸時間就會增加10倍。使用 Big-O 表示法，我們的演算法的複雜度定義為O(N)。最好記住此表示法以供將來參考；它始終用於具有線性複雜度的演算法。請注意：我們在這裡根本不是在討論各種「可變」的事物：網路速度、電腦的功率等等。當評估演算法的複雜性時，這根本沒有意義——無論如何我們都無法控制它。Big-O 評估演算法本身，無論演算法必須在什麼「環境」中運作。 讓我們繼續我們的例子。假設最終要傳輸的檔案大小為 800 TB。如果我們透過網路傳輸，問題當然就解決了。只有一個問題：透過我們大多數人在家中使用的標準現代連結（每秒 100 兆位元）進行傳輸大約需要 708 天。 快2年了！：O 所以，我們的演算法顯然不適合這裡。我們需要一些其他的解決方案！突然，IT巨頭亞馬遜來幫我們了！其 Amazon Snowmobile 服務可讓您將大量資料載入到行動儲存單元中，並透過卡車將它們運送到所需的地址！ 所以我們有一個新的演算法！ “如果您需要以文件形式傳輸信息超過5000公里的距離，並且通過互聯網傳輸該過程需要超過14天，那麼您需要使用亞馬遜卡車運輸。” 14 天的數字是隨機選擇的：假設這是我們可以承受的最長期限。讓我們分析一下我們的演算法。速度怎麼樣？即使卡車的行駛速度僅為 50 公里/小時，只需 100 小時即可行駛 5000 公里。這才四天多啊！這比互聯網傳輸選項要好得多。這個演算法的複雜度怎麼樣？它也是線性的，O(N)嗎？不，不會的。畢竟，卡車並不關心你裝載了多少東西——它仍然會以大致相同的速度行駛並準時到達。無論我們有 800 TB 還是 10 倍的數據，卡車仍將在 5 天內到達那裡。換句話說，透過卡車傳送資料的演算法具有恆定的複雜性。「常數」意味著它不依賴傳遞給演算法的資料。將 1GB 隨身碟放在卡車上，5 天即可到達。將裝有 800 TB 資料的磁碟放在那裡，5 天後就會到達。使用 Big-O 時，恆定複雜度表示為O(1)。由於我們已經熟悉了O(N)和O(1)，現在讓我們看更多「程式設計師」的例子:) 假設給你一個包含 100 個數字的數組，任務是將它們中的每一個印到控制台。for您編寫一個執行此任務的 常規循環

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

編寫的演算法的複雜度是多少？線性，O(N)。 程式必須執行的操作數量取決於傳入其中的數字數量。如果陣列中有 100 個數字，則需要執行 100 個操作（在螢幕上輸出）。如果陣列中有 10,000 個數字，則需要執行 10,000 個操作。我們的演算法可以改進嗎？不。無論如何，我們都必須對數組進行 N 次遍歷並對控制台執行 N 次輸出。讓我們來看另一個例子。

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

我們有一個空的，LinkedList可以在其中插入幾個數字。我們需要估計將單個數字插入到範例中的演算法的複雜性LinkedList，以及它如何依賴列表中的元素數量。答案是O(1) - 恆定的複雜度。為什麼？請注意：每次我們在清單的開頭插入一個數字。此外，正如您所記得的，當數字插入LinkedList元素時，它們不會移動到任何地方 - 連結被重新定義（如果您突然忘記了 LinkedList 是如何工作的，請看一下我們的舊講座之一）。如果現在清單中的第一個數字是 number х，而我們在清單的開頭插入數字 y ，則所需要做的就是：

x.previous  = y;
y.previous = null;
y.next = x;

對於這個參考的重新定義，現在有多少個數字對我們來說並不重要LinkedList──至少一個，至少十億。演算法的複雜度是恆定的 - O(1)。

對數複雜度

不要恐慌！:) 如果「對數」這個詞讓您想結束講座而不繼續閱讀，請等待幾分鐘。這裡不會有數學上的困難（其他地方有很多這樣的解釋），我們將「在手指上」分析所有的例子。想像一下，您的任務是在 100 個數字的陣列中找到一個特定的數字。更準確地說，檢查它是否存在。一旦找到所需的號碼，就必須停止搜索，並且控制台中應顯示“已找到所需的號碼！”條目。它在數組中的索引 = ....” 你會如何解決這樣的問題？這裡的解決方案很明顯：您需要從第一個（或最後一個）開始逐一迭代數組元素，並檢查當前數字是否與所需數字一致。因此，動作的數量直接取決於數組中元素的數量。如果我們有 100 個數字，那麼我們需要轉到下一個元素 100 次並檢查數字是否匹配 100 次。如果有 1000 個數字，那麼就會有 1000 個檢查步驟，這顯然是線性複雜度，O(N)。現在我們將為我們的範例新增一個說明：您需要在其中尋找數字的陣列是按升序排序的。這對我們的任務有什麼改變嗎？我們仍然可以透過暴力搜索來查找所需的數字。但我們可以使用眾所周知的二分查找演算法來代替。 在圖像的第一行中，我們看到一個排序數組。在其中我們需要找到數字 23。我們只需將數組分成 2 部分並檢查數組中的平均數，而不是迭代這些數字。我們找到位於儲存格 4 中的數字並檢查它（圖中的第二行）。這個數字是16，我們正在尋找23。目前的數字更少。這是什麼意思？不需要檢查之前的所有數字（直到數字 16）：它們肯定會小於我們要查找的數字，因為我們的陣列已排序！我們繼續在剩下的 5 個元素中搜尋。 注意：我們只做了一個檢查，但我們已經排除了一半的可能選項。我們只剩下 5 個元素了。我們將重複我們的步驟 - 再次將剩餘數組除以 2，並再次取出中間元素（圖中的第 3 行）。這個數字是 56，比我們要找的還要大。這是什麼意思？我們丟棄另外 3 個選項 - 數字 56 本身，以及它後面的兩個數字（它們肯定大於 23，因為數組已排序）。我們只剩下 2 個數字需要檢查（圖中的最後一行） - 數組索引為 5 和 6 的數字。我們檢查其中的第一個，這就是我們要尋找的 - 數字 23！它的指數=5！讓我們看看演算法的結果，然後我們就會理解它的複雜性。（順便說一句，現在你明白為什麼叫二進位了：它的本質就是不斷地將資料除以2）。結果令人印象深刻！如果我們使用線性搜尋來查找所需的數字，我們將需要 10 次檢查，但使用二分搜尋我們只需 3 次即可完成！在最壞的情況下，如果最後一步我們需要的數字是第二個而不是第一個，那麼就會有 4 個。它的複雜性又如何呢？這是一個非常有趣的點:) 二分搜尋演算法對數組中元素數量的依賴比線性搜尋演算法（即簡單枚舉）要少得多。 陣列中有10 個元素時，線性搜尋最多需要 10 次檢查，二分搜尋最多需要 4 次檢查。相差2.5倍。但對於 1000 個元素的數組，線性搜尋將需要 1000 次檢查，而二分搜尋只需要10 次！差距已經是100倍了！ 注意：陣列中的元素數量增加了 100 倍（從 10 到 1000），而二分查找所需檢查的數量僅增加了 2.5 倍 - 從 4 增加到 10。如果我們達到 10,000 個元素，差異就更令人印象深刻：10,000線性搜尋檢查，二進位檢查總共 14 次。再一次：元素數量增加了 1000 倍（從 10 到 10000），但檢查數量僅增加了 3.5 倍（從 4 到 14）。 二分搜尋演算法的複雜度是對數的，或是用 Big-O 表示法是O(log n)。為什麼這麼叫呢？對數是指數的倒數。二進位對數用於計算 2 的冪。例如，我們需要使用二分搜尋來遍歷 10,000 個元素。 現在你眼前有一張圖片，你知道這最多需要 14 次檢查。但是，如果您眼前沒有任何圖片，並且您需要計算必要檢查的確切數量，該怎麼辦？回答一個簡單的問題就足夠了：應該將數字 2 乘以多少次方才能使獲得的結果 >= 正在檢查的元素數量？ 10000 的 14 次方。2的13次方太小了（8192）但是2的14次方=16384，這個數字滿足我們的條件（它>=數組中元素的數量）。我們找到了對數 - 14。這就是我們需要的檢查次數！:) 演算法及其複雜性是一個太大的話題，無法在一堂講座中涵蓋。但了解這一點非常重要：在很多面試中你都會遇到演算法問題。對於理論，我可以推薦你幾本書。一個很好的起點是「Grocking Algorithms」：雖然書中的範例是用 Python 寫的，但本書的語言和範例非常簡單。對於初學者來說是最好的選擇，而且體積也很小。更嚴肅的閱讀：羅伯特·拉弗雷（Robert Laforet）和羅伯特·塞奇威克（Robert Sedgwick）的書。兩者都是用 Java 編寫的，這將使您的學習變得更容易一些。畢竟，你對這門語言已經很熟悉了！:) 對於具有良好數學背景的學生來說，最好的選擇是Thomas Corman 的書。但你不會只滿足於理論！ 「知道」！=「能夠」 您可以在HackerRank和Leetcode上練習解決演算法問題。其中的問題甚至在 Google 和 Facebook 的面試中也經常使用，所以你絕對不會感到無聊:) 為了強化講座材料，我建議你在 YouTube 上觀看有關 Big-O 的精彩影片。下期講座再見！:)