如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)與算法中的時間與空間復(fù)雜度分析

發(fā)布時間：2022-01-15 13:49:12 來源：億速云閱讀：95 作者：柒染欄目：大數(shù)據(jù)

如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)與算法中的時間與空間復(fù)雜度分析，相信很多沒有經(jīng)驗(yàn)的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

下面主要是對底層的數(shù)據(jù)結(jié)構(gòu)與算法部分進(jìn)行詳盡的講解，今天我們來一起探討一下復(fù)雜度相關(guān)的問題，提到時間復(fù)雜度，不知各位第一反應(yīng)是什么，比如：不就是用時間換取空間，或者用空間來換取時間嗎，恩恩，你說的呢不能算錯。

問題1：什么是算法的復(fù)雜度分析？

我呢，從一下幾個方面進(jìn)行一下闡述：

其一，復(fù)雜度描述的是算法的執(zhí)行時間（或者所占內(nèi)存或者磁盤的空間）與數(shù)據(jù)的規(guī)模的增長之間的一種關(guān)系。

其二，它是要解決：how to 讓計(jì)算機(jī)更加的快速且省存儲空間的情況下解決你所設(shè)定的問題。

其三，評估其性能的指標(biāo)：時間復(fù)雜度和空間復(fù)雜度。

問題2：為什么要進(jìn)行算法的復(fù)雜度分析？

其一，與測試工程師在實(shí)際的生產(chǎn)環(huán)境中做的測試相比較而言，復(fù)雜度的分析不需要執(zhí)行環(huán)境、且易操作、幾乎沒成本。so,作為開發(fā)工程師做復(fù)雜度的分析也是很容易實(shí)現(xiàn)的。

其二，還是我開篇說的那就話，從此你就會遠(yuǎn)離垃圾代碼，讓你在程序員中與眾不同！

問題3:如何進(jìn)行算法的復(fù)雜度分析？

其一，使用大O表示法

算法的執(zhí)行時間與每行代碼的執(zhí)行次數(shù)成正比，用T(n)=O(f(n)),進(jìn)行表示，其中T(n)表示算法執(zhí)行總的時間，f(n)表示每行代碼執(zhí)行的總的次數(shù)，n代表數(shù)據(jù)的規(guī)模。

其二，算法復(fù)雜度分析準(zhǔn)則：

1.單段代碼的時間復(fù)雜度看執(zhí)行次數(shù)最多的那一條或者幾條：比如：for 或者while循環(huán)中的語句。

2.若有很多的代碼，則分析最大循環(huán)嵌套的部分：比如代碼的第1行到10行中只有一個for循環(huán)，在14到30行之間存在for循環(huán)中嵌套for循環(huán)，則此時就要去分析的for循環(huán)嵌套for循環(huán)的這部分內(nèi)容。

3.嵌套代碼求乘積：比如遞歸調(diào)用的代碼，多重循環(huán)的代碼。

4.多個規(guī)模的情況使用加法法則處理。

其三，常見的算法復(fù)雜度：

多項(xiàng)式階：隨著數(shù)據(jù)的規(guī)模的增長，算法的執(zhí)行時間和所占空間，按照多項(xiàng)式的比例增長。eg:

O(1) 常數(shù)階
O(logn) 對數(shù)階
O(n) 線性階
O(nlogn) 線性對數(shù)階
O(n^2) 平方階
O(n^3)立方階

常用的基本就包含這些。

非多項(xiàng)式階：隨著數(shù)據(jù)的規(guī)模的增長，算法的執(zhí)行時間與所占空間暴增，這種的代碼就性能極差了。

主要包括：

O(2^n) 指數(shù)階
O(n!) 階乘階

看完上述內(nèi)容，你們掌握如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)與算法中的時間與空間復(fù)雜度分析的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！

向AI問一下細(xì)節(jié)

猜你喜歡