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