溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
今天給大家介紹一下如何分析數據結構與算法中的時間與空間復雜度指標。文章的內容小編覺得不錯，現在給大家分享一下，覺得有需要的朋友可以了解一下，希望對大家有所幫助，下面跟著小編的思路一起來閱讀吧。
下面主要是對底層的數據結構與算法部分進行詳盡的講解，側重的是度量的幾個維度。
1.最好、最壞情況時間復雜度
最好情況時間復雜度就是，在最理想的情況下，執行一段代碼的時間復雜度。比如一個數組其中有10個元素，我們要找一個元素，當要查找的元素正好是這個數組的第一個元素，這個時候對應的時間復雜度就是最好情況下的時間復雜度。
最壞情況時間復雜度就是，在最糟糕的情況下，執行一段代碼的時間復雜度。正如上面的例子，若要找的這個元素不在這個列表中或者在最后的一個位置，則我們就需要把整個數組遍歷一遍才行，所以這種最糟糕情況下對應的時間復雜度就是最壞情況復雜度。
2.平均情況時間復雜度
我們從上面的第一條中可以感知，最好情況時間復雜度和最壞情況時間復雜度對應的都是極端情況下的代碼復雜度，發生的概率其實并不大。為了更好表示平均情況下的復雜度，我們需要引入另一個概念：平均情況下時間復雜度，我們簡稱平均時間復雜度。
我們就上面的例子分析一下平均情況下的時間復雜度，我們要查找的變量設為X,其在數組中的位置有n+1中情況：在數組的0~n-1位置中和不在數組中。我們把每種情況下需要查找的遍歷的元素個數累加起來，然后再除以n+1，就可以得到需要遍歷的元素個數的平均值，即:(1+2+3+.....+n+n)/(n+1)=n(n+3)/2(n+1)
我們通過上節知道，時間復雜度的大O標記法中，可以省略掉系數、低階、常量，所以，化簡后可得平均時間復雜度就是O(n).
以上就是如何分析數據結構與算法中的時間與空間復雜度指標的全部內容了，更多與如何分析數據結構與算法中的時間與空間復雜度指標相關的內容可以搜索億速云之前的文章或者瀏覽下面的文章進行學習哈！相信小編會給大家增添更多知識,希望大家能夠支持一下億速云！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
