什麼是時間複雜度?
時間複雜度被定義為算法運行所花費的時間，作為輸入長度的函數。它度量算法中執行每條代碼語句所花費的時間。它不會檢查一個算法的總執行時間。相反，當算法中的操作數量(增加或減少)時，它將給出有關執行時間變化(增加或減少)的信息。是的，正如定義所說，所花費的時間隻是輸入長度的函數。
時間複雜度簡介
空間和時間定義了宇宙中的任何物理對象。類似地，空間和時間複雜度可以定義算法的有效性。雖然我們知道在編程中有不止一種方法來解決這個問題，但知道算法如何有效地工作可以為我們的編程方式增加價值。為了找到程序/算法的有效性，知道如何使用空間和時間複雜度來評估它們，可以使程序在所需的最優條件下運行，通過這樣做，它使我們成為高效的程序員。
雖然我們保留空間來理解空間的複雜性，但讓我們在這篇文章中關注時間的複雜性。時間就是金錢!在這篇文章中，您將發現一個算法的時間複雜度的溫和介紹，以及如何基於時間複雜度評估一個程序。
看完這篇文章，你會知道:
讓我們開始吧。
為什麼時間複雜度很重要?
讓我們首先理解什麼定義了算法。
算法，在計算機編程是定義良好的指令的有限序列，通常在計算機中執行，以解決一類問題或執行一項普通任務。根據定義，需要有一個定義的指令序列，必須給計算機執行算法/執行特定的任務。在這種情況下，指令定義的方式可能會發生變化。可以有任意數量的方法，可以定義一組特定的指令來執行相同的任務。此外，由於可以選擇任何一種可用的編程語言，指令可以采用任何形式的語法以及所選編程語言的性能邊界。我們還指出了要在計算機中執行的算法，這導致了在操作係統、處理器、硬件等方麵的下一個變化，這也會影響算法的執行方式。
既然我們知道不同的因素會影響算法執行的結果，那麼明智的做法是了解這些程序在執行任務時的效率如何。為了衡量這一點，我們需要評估算法的空間複雜度和時間複雜度。
根據定義，算法的空間複雜度量化了算法運行所占用的空間或內存的數量，作為輸入長度的函數。而算法的時間複雜度是指算法運行所需的時間與輸入長度的函數關係。既然我們知道了時間複雜性為什麼如此重要，現在是時候理解什麼是時間複雜性以及如何評估它了。
如果你想成為一名程序員，Python是一個很好的實現算法的工具。拿起機器學習證書課程提高你的技能，在你的職業生涯中向前推進。
具體來說，時間複雜度衡量的是執行算法中每個代碼語句所花費的時間。如果一個語句被設置為重複執行，那麼該語句執行的次數等於N乘以每次運行該函數所需的時間。
第一個算法被定義為隻打印一次語句。執行所花費的時間顯示為0納秒．雖然第二個算法被定義為打印相同的語句，但這一次它被設置為在FOR循環中運行相同的語句10次。在第二種算法中，執行代碼行FOR循環和print語句所花費的時間為2毫秒．而且，隨著N值的增加，所花費的時間也會增加，因為語句將被執行N次。
注意:此代碼運行在Python-Jupyter Notebook上，Windows 64位操作係統+處理器英特爾酷睿i7 ~ 2.4GHz。以上時間值可能因不同的硬件、不同的操作係統和不同的編程語言(如果使用的話)而不同。
到目前為止，您可能已經得出結論，當算法使用隻執行一次的語句時，將總是需要相同的時間，並且當語句處於循環條件時，所需的時間將根據設置運行循環的次數而增加。而且，當一個算法同時包含單個執行語句和LOOP語句或嵌套LOOP語句時，時間會根據每個語句執行的次數成比例地增加。
這導致我們提出下一個問題，關於如何確定輸入和時間之間的關係，給定一個算法中的語句。為了定義這一點，我們將看看每個語句如何獲得一個描述時間複雜度的符號順序，稱為大O符號．
有哪些不同類型的時間複雜度符號?
正如我們所看到的，時間複雜度是由時間作為輸入長度的函數給出的。並且，在輸入數據大小(n)和執行的操作數量(n)之間存在相對於時間的關係。這種關係被表示為時間複雜度的增長順序，並給出符號O[n]，其中O是增長的順序，n是輸入的長度。它也被稱為“大O符號”
大O符號表示算法的運行時間，它通過定義對輸入“n”進行n次操作來表示算法相對於輸入“n”的增長速度。因此，算法的時間複雜度是由為每一行函數分配的所有O[n]的組合表示。
這裏有不同類型的時間複雜度，讓我們逐個來看:
1.常數時間- O (1)
2.線性時間- O (n)
3.對數時間- O (log n)
4.二次時間- O (n²)
5.立方時間- O (n^3)
還有很多更複雜的符號，比如指數時間，擬線性時間，階乘時間，等等。根據定義的函數類型使用。
常數時間- O (1)
當一個算法不依賴於輸入大小n時，它被稱為O(1)階常數時間。不管輸入大小n如何，運行時總是相同的。
上麵的代碼表明，無論數組(n)的長度如何，在任意長度的數組中獲取第一個元素的運行時都是相同的。如果將運行時間視為1個單位的時間，那麼運行兩個數組隻需要1個單位的時間，而不考慮長度。因此，函數處於O(1)階的常數時間下。
線性時間- O(n)
當一個算法的運行時間隨著輸入的長度線性增加時，它被稱為具有線性時間複雜度。當函數涉及檢查輸入數據中的所有值時，順序為O(n)。
上麵的代碼表明，基於數組的長度(n)，運行時間將線性增加。如果將運行時間視為1個單位的時間，則運行該數組隻需要n乘以1個單位的時間。因此，該函數隨輸入大小線性運行，且為O(n)階。
對數時間- O (log n)
當一個算法在每一步中減少輸入數據的大小時，它被稱為具有對數時間複雜度。這表明操作的次數與輸入的大小不相同。操作的數量隨著輸入大小的增加而減少。算法可以在二叉樹或者二分搜索函數。這涉及到在數組中搜索給定值，方法是將數組分成兩個，並在一個分割中開始搜索。這可以確保不是對數據的每個元素都執行操作。
二次時間- O (n²)
一個算法被稱為具有非線性時間複雜度，其中運行時間隨著輸入長度的非線性(n^2)增加。一般來說，嵌套循環的順序是這樣的，其中一個循環需要O(n)，如果函數包含一個循環中的循環，那麼它的順序是O(n)*O(n) = O(n²)。
類似地，如果函數中定義了' m '個循環，則順序由O (n ^ m)給出，這些循環被調用多項式時間複雜度功能。
因此，上麵的插圖給出了每個函數如何根據運行時與輸入數據大小的數量和對它們執行的操作數量之間的關係獲得順序符號的合理想法。
如何計算時間複雜度?
我們已經看到了如何給出每個函數的順序符號，以及操作的運行時與no、輸入大小之間的關係。現在，是時候知道如何根據每個操作和輸入大小的順序符號來評估算法的時間複雜度，並計算給定n運行算法所需的總運行時間。
讓我們用一個例子來說明如何評估一個算法的時間複雜度:
算法定義為:
1.給定2個輸入矩陣，它是一個n階的方陣
2.兩個矩陣中每個元素的值都是使用np隨機選擇的。隨機函數
3.最初分配一個結果矩陣，其中0個值的順序等於輸入矩陣的順序
4.X的每個元素乘以Y的每個元素，結果值存儲在結果矩陣中
5.然後將結果矩陣轉換為列表類型
6.對於結果列表中的每個元素，都將相加以給出最終答案
讓我們假設成本函數C是運行一個函數所花費的單位時間，而“n”表示在算法中定義的語句運行的次數。
例如，如果運行print函數所花費的時間是1微秒(C)，如果算法被定義為運行print函數1000次(n)，
則總運行時間= (C *N) = 1微秒*1000 = 1毫秒
每一行的運行時間為:
Line 1 = C1 * 1 Line 2 = C2 * 1 Line 3,4,5 = (C3 * 1) + (C3 * 1) + (C3 * 1) Line 6,7,8 = (C4*[n+1]) * (C4*[n+1]) Line 9 = C4*[n] Line 10 = C5 * 1 Line 11 = C2 * 1 Line 12 = C4*[n+1] Line 13 = C4*[n] Line 14 = C2 * 1 Line 15 = C6 * 1
總運行時間= (C1 * 1) + 3 (C2 * 1) + 3 (C3 * 1) + (C4 * (n + 1) * (C4 * (n + 1) * (C4 * (n + 1)) + (C4 * [n]) + (C5 * 1) + (C4 * (n + 1)) + (C4 * [n]) + (C6 * 1)
用C替換所有代價來估計符號的順序，
總運行時間
= C + 3 C + 3 C + C (n + 1) * (n + 1) * (n + 1) C) + nC + C + C (n + 1) + nC + C = 7 C + C (n ^ 3) + 3 (n ^ 2) C + 3數控+ C + 3數控12 + 3 C = C + C (n ^ 3) + 3 (n ^ 2) C + 6數控= C (n ^ 3) + C (n ^ 2) + C (n) + C = O (n ^ 3) + O (n ^ 2) + O (n) + O (1)
通過將所有代價函數替換為C，我們可以得到輸入大小的度為3，這表示了該算法的時間複雜度的順序。在這裏，從最後的方程中，很明顯，運行時間隨輸入大小的多項式函數“n”而變化，因為它與輸入大小的三次、二次和線性形式有關。
這就是如何為任何給定的算法評估順序，以及如果輸入大小增加或減少，如何估計它在運行時方麵的擴展。還要注意，為了簡單起見，所有的成本值，如C1, C2, C3等都用C代替，以了解符號的順序。在實時中，我們需要知道每個C的值，這可以給出給定輸入值“n”的算法的準確運行時間。
排序算法的時間複雜度
了解排序算法的時間複雜性有助於我們在某種情況下選擇最佳的排序技術。以下是一些排序技巧:
插入排序的時間複雜度是多少?
的時間複雜度插入排序最好的情況是O(n)在最壞的情況下，時間複雜度是O(n²)。
歸並排序的時間複雜度是多少?
這種排序技術適用於各種情況。歸並排序最好的情況是O(nlogn)在最壞的情況下，時間複雜度為O(nlogn)。這是因為歸並排序對所有類型的情況實現了相同數量的排序步驟。
冒泡排序的時間複雜度是多少?
的時間複雜度冒泡排序最好的情況是O(n)在最壞的情況下，時間複雜度是O(n²)。
W快速排序的時間複雜度是多少?
最佳情況下的快速排序是O(nlogn)。在最壞的情況下，時間複雜度是O(n²)。快速排序被認為是最快的排序算法，因為它在最佳和平均情況下的性能為O(nlogn)。
搜索算法的時間複雜度
現在讓我們深入研究一些搜索算法的時間複雜性，並了解它們中哪一個更快。
線性搜索的時間複雜度:
線性搜索遵循順序訪問。線性搜索在最佳情況下的時間複雜度為O(1)。在最壞的情況下，時間複雜度為O(n)。
二叉搜索的時間複雜度:
二分搜索是兩種搜索算法中速度較快的一種。然而，對於較小的數組，線性搜索做得更好。二叉搜索在最佳情況下的時間複雜度為O(1)。最壞的情況下，時間複雜度是O(log n)。
空間複雜度
你可能聽說過這個術語，“空間複雜性”，它在談論時間複雜性時徘徊。什麼是空間複雜性?它是任何算法都需要的工作空間或存儲空間。它直接依賴於或正比於算法的輸入量。要計算空間複雜度，你所要做的就是計算算法中變量所占用的空間。空間越小，算法執行越快。同樣重要的是，要知道時間和空間的複雜性是相互無關的。
總結
在這篇博客中，我們介紹了時間複雜度的基本概念，以及為什麼我們需要在我們設計的算法中使用它的重要性。此外，我們還了解了用於各種函數的不同類型的時間複雜度，最後，我們學習了如何根據代價函數和語句被定義運行的次數為任何算法分配符號的順序。
鑒於VUCA世界和時代的條件大數據在當今世界，數據流量每秒鍾都在無條件地增加，設計一種有效的算法來執行特定的任務是當務之急。並且，在給定的輸入數據大小下，了解算法的時間複雜度，可以幫助我們高效地規劃我們的資源，處理和提供結果。因此，了解算法的時間複雜度可以幫助你做到這一點，也可以讓你成為一個有效的程序員。編碼快樂!
請在下方評論中留下您的疑問，我們會盡快回複您。
