[導(dǎo)讀]一個語句的頻度是指該語句在算法中被重復(fù)執(zhí)行的次數(shù)。算法中所有語句的頻度之和記為T(n)，它是該算法問題規(guī)模n的函數(shù)，時間復(fù)雜度主要分析T(n)的數(shù)量級。算法中基本運(yùn)算(最深層循環(huán)內(nèi)的語句)的頻度與Tn)同數(shù)量級，因此通常采用算法中基本運(yùn)算的頻度fn)來分析算法的時間復(fù)雜度3。
算法的時間復(fù)雜度取決于問題的規(guī)模，待處理數(shù)據(jù)的初態(tài)。
一個語句的頻度是指該語句在算法中被重復(fù)執(zhí)行的次數(shù)。算法中所有語句的頻度之和記為T(n)，它是該算法問題規(guī)模n的函數(shù)，時間復(fù)雜度主要分析T(n)的數(shù)量級。算法中基本運(yùn)算(最深層循環(huán)內(nèi)的語句)的頻度與Tn)同數(shù)量級，因此通常采用算法中基本運(yùn)算的頻度fn)來分析算法的時間復(fù)雜度3。
算法的時間復(fù)雜度記為：T(n)= O(fn))式中，О 的含義是T(n)的數(shù)量級，其嚴(yán)格的數(shù)學(xué)定義是:若T(n)和fn)是定義在正整數(shù)集合上的兩個函數(shù)，則存在正常數(shù)C和n，使得當(dāng)n≥no時，都滿足0≤T(n)≤Cfn)。
算法的時間復(fù)雜度不僅依賴于問題的規(guī)模n，也取決于待輸入數(shù)據(jù)的性質(zhì)(如輸入數(shù)據(jù)元素的初始狀態(tài))。
下載文檔
