數據結構與算法時間複雜度

NO IMAGE
目錄

一、數據結構概要
二、算法概要
三、時間複雜度簡介
四、求解時間複雜度

一、數據結構

       數據結構 是相互之間存在一種或多種特定關係的數據元素的集合。在各類實際應用問題中,數據元素之間總是存在著各種關係,描述數據元素之間關係的方法稱為結構。通常,可根據數據元素之間所存在的關係的不同特徵,用4類基本結構予以描述:
(1)集合:指結構中的數據元素之間只存在“同屬一個集合”的關係。

(2)線性結構:指結構中的數據元素之間存在“一個對一個”的關係。

(3)樹形結構:指結構中的數據元素之間存在“一個對多個”的關係。
(4)圖形結構:指結構中的數據兀素之間存在“多個對多個”的關係。

數據結構與算法時間複雜度

二、算法

2.1、算法定義:

       通常,算法( Algorithm)是指解決問題的一種方法或一個過程。如果把問題看作函數,則算法就能把輸入轉化成輸出。在數據結構中,算法是對特定問題求解步驟的一種描述,是指令的有限序列。
       同一問題可以有多種不同的求解算法,一個給定的算法可以用來描述解決特定問題的一個具體的求解方案。瞭解對於同一問題的多種求解法有助於對算法的運行效率進行分析和比較,加深對算法的理解。

2.2、算法設計:

        算法設計技術 是用算法解題的一般性方法,用於解決不同計算領域的多種問題。常用的算法設計技術主要有蠻力法、分治法、減治法、變治法、時空權衡、動態規劃、貪婪技術等

1、蠻力法
       蠻力法是一種簡單直接地解決問題的方法,常常直接基於問題的描述和所涉及的概念定義。可以應用蠻力法解決廣闊領域的各種問題,它是唯一一種幾乎什麼問題都能解決的一般性方法。

2、分治法
       分治法將問題的實例劃分為若干個較小的實例,對這些較小實例遞歸求解,然後合併這些解,以得到原始問題的解。

3、減治法
       減治法通過建立一個問題給定實例的解和同樣問題較小實例解的關係,採用自頂向下(遞歸)或自底向上(非遞歸)的策略進行求解。
       減治法有三個主要的變種:減一技術(每次迭代減去一個常量,通常為1)、減半技術(每次選代減去一個常量因子,通常為2)、減可變規模技術(每次選代規模減小的模式不同)。

4、變治法
       變治法基於變換的思想,將問題變換成更容易求解的形式。
       變治法有三個策略:實例化簡(把問題的實例變換為相同問題的另一個實例,使問題的求解更加容易)、改變表現(將一個問題實例的表現改變為同樣實例的另一種表現)、問題化簡(把一個給定的問題變換成另一個可以用已知算法求解的問題)

5、時空權衡
       時空權衡主要有空間換時間和時間換空間兩種技術。在早期的計算機應用中,硬件資源限制嚴重,許多問題包含的大量數據無法整體裝入計算機中一次處理,需要通過時間換空間技術才能解決;但在硬件資源十分豐富的現在,算法設計通常採用空間換時間技術。
       空間換時間技術有兩類,輸入增強技術,通過對問題輸入的部分或全部做預處理,以來提高算法的時間效率,加速問題的求解;預構造技術,通過使用額外的空間來實現更快或更方便的數據存取。

6、動態規劃
       動態規劃是一種對具有交疊子問題的問題進行求解的技術。一般來說,這樣的子問題出現在求解給定問題的遞推關係中,而該遞推關係包含了相同類型更小問題的解。它通過對每個較小的子問題求解一次並記錄在表中,從而避免對交疊子問題的重複求解,從表中得出原始問題的解。

7、貪婪技術
       貪婪技術通過一系列步驟來構造問題的解,每一步對目前構造的部分解做一個擴展,直到獲得問題的完整解為止。貪婪技術核心是,所做的每一步選擇都必須滿足可行、局部最優和不可取消原則。

2.3、算法分析

       估量一個算法或計算機程序效率的方法,稱為 算法分析。所謂算法分析,就是對一個算法所消耗的資源的估算。算法分析 的目的主要是考察算法的時間效率和空間需求,分別從算法的 時間複雜度空間複雜度 兩個方面進行分析,如果存在多個可行的算法,則根據 時間複雜度或空間複雜度 這兩個指標選取效率最高最優的算法。

進行算法分析需要了解的基本概念:
(1)問題規模:一般是指輸入量的數目。
(2)基本操作:通常是指具有完成該操作所需的時間與操作數的取值無關的性質的操作。
(3)代價:即實現一個算法所需的資源需求。
(4)增長率:是指當問題規模增大時,算法代價增長的速率。
(5)最佳、最差和平均代價:分別是指算法實現對資源需求的最小、最大和平均情況。

三、時間複雜度

        算法的時間複雜度 是指算法對時間的需求。一個算法的運行時間通常與所解決問題的規模大小有關。
       例如,在排序問題中,排序的元素個數n就是問題規模,排序算法中基本操作語句的重複執行次數隨著問題規模n的增大而增加。
       一般情況下,算法中基本操作重複執行的次數T(n)是問題規模n的某個函數f(n)。因此,算法的時間效率可記為: T(n)= O(f(n))
表示隨問題規模n的增大,算法的執行時間的增長率和f(n)的增長率相同,稱作算法的漸近時間複雜度,簡稱時間複雜度 。表達式中O的含義是指T(n)的數量級。一般情況下,當Tn)為多項式時,可只取最高次冪項,且係數也可省略。例如:T(n)=3n²+n-9 則T(n)=O(n²)。
       一般地,算法所消耗的時間是每條語句的執行時間之和。每條語句的執行時間是其執行次數(頻度)與該語句執行一次所需時間的乘積。在計算機中,程序語句的執行時間與計算機的性能有關,因此在分析算法的執行效率時,假設語句執行時間與機器無關,只考慮所有語句的執行次數。
       算法中的基本操作可以理解為算法程序中最深層循環內的語句中的基本操作,它的執行次數(頻度)與包含它的語句的執行次數相同。

       通常情況下,時間複雜度的表示以O(f(n))形式體現,如O(1)、O(n)、O(n²)、O(log n)、O(2^n )等。根據f(n)的具體形式,常稱某個算法的時間複雜度是常量階O(1)線性階O(n)、平方階O(n²)、對數O(log n)、指數階O(2^n)等。常數階表示算法的時間複雜度與問題規模n無關。當一個算法的時間複雜度體現為指數階時,通常將認為不是一個有效的算法。

T(n)與n的最高階數關係名稱
T(n)=O(1)常數階
T(n)=O(n)線性階
T(n)=O(n²)平方階
T(n)=O(n³)立方階
T(n)=O(2^n )指數階
T(n)=O(log n)對數階
T(n)=O(n log n)n log n階

        ***空間複雜度***是指算法執行過程對計算機存儲空間的要求,稱為算法的空間複雜度。類似於時間複雜度,記為 S(n)= O(f(n)) 其中n是問題的規模。
       通常,執行一個算法程序除了需要存儲空間存放本身所用的指令、常數、變量和輸出數據外,還需要一些輔助空間用於對數據進行處理及存儲處理過程中的中間信息。若輸入數據所佔的空間只取決於問題本身而與算法無關,則只需要分析除了輸入和程序之外的輔助空間需求。算法的空間複雜度通常就是指這種輔助空間需求的大小。

四、求解時間複雜度

最後通過實例來加深對時間複雜度的理解:

  • 【例1】以下算法實現奇偶性判斷,試分析時間複雜度。
int isOdd (int n) {
if(n % 2 == 0) {   //(1)
return 1:         //(2)
}else {
return 0;  //(3)
}
}
分析:語句(1)執行1次,根據表達式n%2==0結果,可能執行語句(2)或語句(3)1次。
語句總執行次數為T(n)=1+1=2
因此,算法的時間複雜度為常數階O(1)。算法的執行時間與問題規模n無關。
  • 【例2】遞歸算法實現求n!,試分析時間複雜度。
int func(int n) {
if(n <= 1) {
return 1;  //(1)
}else {
return(n * func(n-1));  //(2)
}
}
分析:語句(1)的時間複雜度為O(1),遞歸調用fact(n-1)的時間是T(n-1),因此可得
當n≤1時,T(n) = O(1),
當n>1時:T(n) = T(n-1) + O(1),T(n-1)=0(1)+T(n-2),T(n-2)=O(1)+T(n-3)........
由此可推出
T(n)=(n-1)0(1)+T(1)=O(n)
因此遞歸求n!算法的時間複雜度為O(n)。

相關文章

IOS組件化方案總結

數據結構與算法查找

數據結構與算法樹形結構

數據結構與算法線性表