下述演算法的時間發雜度Tn

『壹』 某演算法的時間復雜度為O(n),表明該演算法的：

C、執行時間與n成正比。

A選項，演算法的時間復雜度與問題規模沒有任何關系。故A選項錯誤。

B選項，任何演算法的執行時間都幾乎不可能完全等於。故B選項錯誤。

C選項，如果一個演算法的時間復雜度為，的值增加，的值也會隨之增加，那麼執行時間肯定就是與成正比的。故C選項正確。

D選項，一個演算法的時間復雜度與這個問題的數據規模沒有關系，故D選項也錯誤。

(1)下述演算法的時間發雜度Tn擴展閱讀：

演算法的時間復雜度通常用大O符號表述，定義為T[n] = O(f(n))。稱函數T(n)以f(n)為界或者稱T(n)受限於f(n)。

如果一個問題的規模是n，解這一問題的某一演算法所需要的時間為T(n)。T(n)稱為這一演算法的「時間復雜度」。當輸入量n逐漸加大時，時間復雜度的極限情形稱為演算法的「漸近時間復雜度」。

『貳』 確定下列演算法中語句的執行次數，並給出演算法的時間復雜度

int n=10,cout=0; 執行1次 ,時間復雜度Tn=O(1),
for(int i=1;i<=n;i++) 執行（n+1）次，原操作時間復雜度Tn=O(n) ，
for(int j=1;j<=i;j++) 執行1+2+3+...+n=1/2(n²+n)次， 原操作時間復雜度Tn=O(n²) ,
for(int k=1;k<=j;k++) 執行1+(1+2)+(1+2+3)+...+[1/2(n²+n)]=1/6(n³+3n²+2n)次，n的最高次冪是3，原操作時間復雜度Tn=O(n³)，
cout ++;（原操作） 執行1+(1+2)+(1+2+3)+...+[1/2(n²+n)]=1/6(n³+3n²+2n)次，原操作時間復雜度Tn=O(n³)

『叄』 綆楁硶鐨勫嶆潅搴︿富瑕佸寘鎷

綆楁硶鐨勫嶆潅搴︿富瑕佸寘鎷鏃墮棿澶嶆潅搴﹀拰絀洪棿澶嶆潅搴︺

綆楁硶鐨勬椂闂村嶆潅搴﹀拰絀洪棿澶嶆潅搴﹀悎縐頒負綆楁硶鐨勫嶆潅搴︺

鏃墮棿澶嶆潅搴︼細鏃墮棿澶嶆潅搴︽槸鎸囨墽琛岀畻娉曟墍闇瑕佺殑璁＄畻宸ヤ綔閲忋

絀洪棿澶嶆潅搴︼細鏄瀵逛竴涓綆楁硶鍦ㄨ繍琛岃繃紼嬩腑涓存椂鍗犵敤瀛樺偍絀洪棿澶у皬鐨勯噺搴︺

綆楁硶鐨勫嶆潅鎬т綋榪愯岃ョ畻娉曟椂鐨勮＄畻鏈烘墍闇璧勬簮鐨勫氬皯涓婏紝璁＄畻鏈鴻祫婧愭渶閲嶈佺殑鏄鏃墮棿鍜岀┖闂達紙鍗沖瘎瀛樺櫒錛夎祫婧愶紝鍥犳ゅ嶆潅搴﹀垎涓烘椂闂村拰絀洪棿澶嶆潅搴︺

澶嶆潅搴﹀垎鏋愶細

閫氬父涓涓綆楁硶鐨勫嶆潅搴︽槸鐢卞叾杈撳叆閲忓喅瀹氱殑錛岄殢鐫杈撳叆鐨勫炲姞錛屼笉鍚岀畻娉曠殑澶嶆潅搴﹀為暱閫熷害涓轟簡闄嶄綆綆楁硶澶嶆潅搴︼紝搴斿綋鍚屾椂鑰冭檻鍒拌緭鍏ラ噺錛岃捐¤緝濂界殑綆楁硶銆

鍚屼竴闂棰樺彲鐢ㄤ笉鍚岀畻娉曡В鍐籌紝鑰屼竴涓綆楁硶鐨勮川閲忎紭鍔ｅ皢褰卞搷鍒扮畻娉曚箖鑷崇▼搴忕殑鏁堢巼銆傜畻娉曞垎鏋愮殑鐩鐨勫湪浜庨夋嫨鍚堥傜畻娉曞拰鏀硅繘綆楁硶銆備竴涓綆楁硶鐨勮瘎浠蜂富瑕佷粠鏃墮棿澶嶆潅搴﹀拰絀洪棿澶嶆潅搴︽潵鑰冭檻銆

『肆』 演算法的時間復雜度取決於什麼

演算法的時間復雜度取決於問題的規模，待處理數據的初態。

一個語句的頻度是指該語句在演算法中被重復執行的次數。演算法中所有語句的頻度之和記為T(n)，它是該演算法問題規模n的函數，時間復雜度主要分析T(n)的數量級。演算法中基本運算（最深層循環內的語句）的頻度與Tn)同數量級，因此通常採用演算法中基本運算的頻度fn)來分析演算法的時間復雜度3。

演算法的時間復雜度記為：T(n)= O(fn))式中，О 的含義是T(n)的數量級，其嚴格的數學定義是:若T(n)和fn)是定義在正整數集合上的兩個函數，則存在正常數C和n，使得當n≥no時，都滿足0≤T(n)≤Cfn)。

演算法的時間復雜度不僅依賴於問題的規模n，也取決於待輸入數據的性質（如輸入數據元素的初始狀態)。

『伍』 一道經典的面試題：如何從N個數中選出最大（小）的n個數

這個問題我前前後後考慮了有快一年了，也和不少人討論過。據我得到的消息，Google和微軟都面過這道題。這道題可能很多人都聽說過，或者知道答案（所謂的堆），不過我想把我的答案寫出來。我的分析也許存有漏洞，以交流為目的。但這是一個滿復雜的問題，蠻有趣的。看完本文，也許會啟發你一些沒有想過的解決方案（我一直認為堆也許不是最高效的演算法）。在本文中，將會一直以尋找n個最大的數為分析例子，以便統一。註：本文寫得會比較細節一些，以便於絕大多數人都能看懂，別嫌我羅嗦:) 我很不確定多少人有耐心看完本文！ Naive 方法： 首先，我們假設n和N都是內存可容納的，也就是說N個數可以一次load到內存里存放在數組里（如果非要存在鏈表估計又是另一個challenging的問題了）。從最簡單的情況開始，如果n=1，那麼沒有任何疑惑，必須要進行N-1次的比較才能得到最大的那個數，直接遍歷N個數就可以了。如果n=2呢？當然，可以直接遍歷2遍N數組，第一遍得到最大數max1，但是在遍歷第二遍求第二大數max2的時候，每次都要判斷從N所取的元素的下標不等於max1的下標，這樣會大大增加比較次數。對此有一個解決辦法，可以以max1為分割點將N數組分成前後兩部分，然後分別遍歷這兩部分得到兩個最大數，然後二者取一得到max2。 也可以遍歷一遍就解決此問題，首先維護兩個元素max1，max2（max1=max2），取到N中的一個數以後，先和max1比，如果比max1大（則肯定比max2大），直接替換max1，否則再和max2比較確定是否替換max2。採用類似的方法，對於n=2，3，4一樣可以處理。這樣的演算法時間復雜度為O（nN）。當n越來越大的時候（不可能超過N/2，否則可以變成是找N-n個最小的數的對偶問題），這個演算法的效率會越來越差。但是在n比較小的時候（具體多小不好說），這個演算法由於簡單，不存在遞歸調用等系統損耗，實際效率應該很不錯. 堆：當n較大的時候採用什麼演算法呢？首先我們分析上面的演算法，當從N中取出一個新的數m的時候，它需要依次和max1，max2，max3max n比較，一直找到一個比m小的max x，就用m來替換max x，平均比較次數是n/2。可不可以用更少的比較次數來實現替換呢？最直觀的方法是，也就是網上文章比較推崇的堆。堆有這么一些好處：1.它是一個完全二叉樹，樹的深度是相同節點的二叉樹中最少的，維護效率較高；2.它可以通過數組來實現，而且父節點p與左右子節l，r點的數組下標的關系是s[l] = 2*s[p]+1和s[r] = 2*s[p]+2。在計算機中2*s[p]這樣的運算可以用一個左移1位操作來實現，十分高效。再加上數組可以隨機存取，效率也很高。3.堆的Extract操作，也就是將堆頂拿走並重新維護堆的時間復雜度是O（logn），這里n是堆的大小。 具體到我們的問題，如何具體實現呢？首先開辟一個大小為n的數組區A，從N中讀入n個數填入到A中，然後將A維護成一個小頂堆（即堆頂A[0]中存放的是A中最小的數）。然後從N中取出下一個數，即第n+1個數m，將m與堆頂A[0]比較，如果m<=A[0]，直接丟棄m。否則應該用m替換A[0]。但此時A的堆特性可能已被破壞，應該重新維護堆：從A[0]開始，將A[0]與左右子節點分別比較（特別注意，這里需要比較兩次才能確定最大數，在後面我會根據這個來和敗者樹比較），如果A[0]比左右子節點都小，則堆特性能夠保證，勿需繼續，否則如左（右）節點最大，則將A[0]與左（右）節點交換，並繼續維護左（右）子樹。依次執行，直到遍歷完N，堆中保留的n個數就是N中最大的n個數。 這都是堆排序的基本知識，唯一的trick就是維護一個小頂堆，而不是大頂堆。不明白的稍微想一下。維護一次堆的時間復雜度為O（logn），總體的復雜度是O（Nlogn）這樣一來，比起上面的O（nN），當n足夠大時，堆的效率肯定是要高一些的。當然，直接對N數組建堆，然後提取n次堆頂就能得到結果，而且其復雜度是O（nlogN）,當n不是特別小的時候這樣會快很多。但是對於online數據就沒辦法了，比如N不能一次load進內存，甚至是一個流，根本不知道N是多少。 敗者樹：有沒有別的演算法呢？我先來說一說敗者樹（loser tree）。也許有些人對loser tree不是很了解，其實它是一個比較經典的外部排序方法，也就是有x個已經排序好的文件，將其歸並為一個有序序列。敗者樹的思想咋一看有些繞，其實是為了減小比較次數。首先簡單介紹一下敗者樹：敗者樹的葉子節點是數據節點，然後兩兩分組（如果節點總數不是2的冪，可以用類似完全樹的結構構成樹），內部節點用來記錄左右子樹的優勝者中的敗者（注意記錄的是輸的那一方），而優勝者則往上傳遞繼續比較，一直到根節點。如果我們的優勝者是兩個數中較小的數，則根節點記錄的是最後一次比較中的敗者，也就是所有葉子節點中第二小的那個數，而最小的那個數記錄在一個獨立的變數中。這里要注意，內部節點不但要記錄敗者的數值，還要記錄對應的葉子節點。如果是用鏈表構成的樹，則內部節點需要有指針指向葉子節點。這里可以有一個trick，就是內部節點只記錄敗者對應的葉子節點，具體的數值可以在需要的時候間接訪問（這一方法在用數組來實現敗者樹時十分有用，後面我會講到）。關鍵的來了，當把最小值輸出後，最小值所對應的葉子節點需要變成一個新的數（或者改為無窮大，在文件歸並的時候表示文件已讀完）。接下來維護敗者樹，從更新的葉子節點網上，依次與內部節點比較，將敗者更新，勝者往上繼續比較。由於更新節點佔用的是之前的最小值的葉子節點，它往上一直到根節點的路徑與之前的最小值的路徑是完全相同的。內部節點記錄的敗者雖然稱為敗者，但卻是其所在子樹中最小的數。也就是說，只要與敗者比較得到的勝者，就是該子樹中最小的那個數（這里講得有點繞了，看不明白的還是找本書看吧，對照著圖比較容易理解）。 註：也可以直接對N構建敗者樹，但是敗者樹用數組實現時不能像堆一樣進行增量維護，當葉子節點的個數變動時需要完全重新構建整棵樹。為了方便比較堆和敗者樹的性能，後面的分析都是對n個數構建的堆和敗者樹來分析的。 總而言之，敗者樹在進行維護的時候，比較次數是logn+1。與堆不同的是，敗者樹是從下往上維護，每上一層，只需要和敗者節點比較一次即可。而堆在維護的時候是從上往下，每下一層，需要和左右子節點都比較，需要比較兩次。從這個角度，敗者樹比堆更優一些。但是，請注意但是，敗者樹每一次維護必定需要從葉子節點一直走到根節點，不可能中間停止；而堆維護時，有可能會在中間的某個層停止，不需要繼續往下。這樣一來，雖然每一層敗者樹需要的比較次數比堆少一倍，但是走的層數堆會比敗者樹少。具體少多少，從平均意義上到底哪一個的效率會更好一些？那我就不知道了，這個分析起來有點麻煩。感興趣的人可以嘗試一下，討論討論。但是至少說明了，也許堆並非是最優的。 具體到我們的問題。類似的方法，先構建一棵有n個葉子節點的敗者樹，勝出者w是n個中最小的那一個。從N中讀入一個新的數m後，和w比較，如果比w小，直接丟棄，否則用m替換w所在的葉子節點的值，然後維護該敗者樹。依次執行，直到遍歷完N，敗者樹中保留的n個數就是N中最大的n個數。時間復雜度也是O（Nlogn） 類快速排序方法： 快速排序大家大家都不陌生了。主要思想是找一個軸節點，將數列交換變成兩部分，一部分全都小於等於軸，另一部分全都大於等於軸，然後對兩部分遞歸處理。其平均時間復雜度是O（NlogN）。從中可以受到啟發，如果我們選擇的軸使得交換完的較大那一部分的數的個數j正好是n，不也就完成了在N個數中尋找n個最大的數的任務嗎？當然，軸也許不能選得這么恰好。可以這么分析，如果jn，則最大的n個數肯定在這j個數中，則問題變成在這j個數中找出n個最大的數；否則如果j<n，則這j個數肯定是n個最大的數的一部分，而剩下的j-n個數在小於等於軸的那一部分中，同樣可遞歸處理。 需要注意的是，這里的時間復雜度是平均意義上的，在最壞情況下，每次分割都分割成1：N-2，這種情況下的時間復雜度為O（n）。但是我們還有殺手鐧，可以有一個在最壞情況下時間復雜度為O（N）的演算法，這個演算法是在分割數列的時候保證會按照比較均勻的比例分割，at least 3n/10-6。具體細節我就不再說了，感興趣的人參考演算法導論（Introction to Algorithms 第二版第九章 Medians and Orders Statistics）。 還是那個結論，堆不見得會是最優的。 本文快要結束了，但是還有一個問題：如果N非常大，存放在磁碟上，不能一次裝載進內存呢？怎麼辦？對於介紹的Naive方法，堆，敗者樹等等，依然適用，需要注意的就是每次從磁碟上盡量多讀一些數到內存區，然後處理完之後再讀入一批。減少IO次數，自然能夠提高效率。而對於類快速排序方法，稍微要麻煩一些：分批讀入，假設是M個數，然後從這M個數中選出n個最大的數緩存起來，直到所有的N個數都分批處理完之後，再將各批次緩存的n個數合並起來再進行一次類快速排序得到最終的n個最大的數就可以了。在運行過程中，如果緩存數太多，可以不斷地將多個緩存合並，保留這些緩存中最大的n個數即可。由於類快速排序的時間復雜度是O（N），這樣分批處理再合並的辦法，依然有極大的可能會比堆和敗者樹更優。當然，在空間上會佔用較多的內存。 總結：對於這個問題，我想了很多，但是覺得還有一些地方可以繼續深挖：1. 堆和敗者樹到底哪一個更優？可以通過理論分析，也可以通過實驗來比較。也許會有人覺得這個很無聊；2. 有沒有近似的演算法或者概率演算法來解決這個問題？我對這方面實在不熟悉，如果有人有想法的話可以一塊交流。如果有分析錯誤或遺漏的地方，請告知，我不怕丟人，呵呵！最後請時刻謹記，時間復雜度不等於實際的運行時間，一個常數因子很大的O（logN）演算法也許會比常數因子小的O（N）演算法慢很多。所以說，n和N的具體值，以及編程實現的質量，都會影響到實際效率。

『陸』 演算法的時間復雜度是指什麼

演算法的時間復雜度是指：執行程序所需的時間。

一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近無窮大時。

T(n)/f(n)的極限值為不等於零的常數，則稱為f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為演算法的漸進時間復雜度，簡稱時間復雜度。比如：

在 T(n)=4nn-2n+2 中，就有f(n)=nn，使得T(n)/f(n)的極限值為4，那麼O(f(n))，也就是時間復雜度為O(n*n)。

時間復雜度中大O階推導是：

推導大O階就是將演算法的所有步驟轉換為代數項，然後排除不會對問題的整體復雜度產生較大影響的較低階常數和系數。

有條理的說，推導大O階，按照下面的三個規則來推導，得到的結果就是大O表示法：運行時間中所有的加減法常數用常數1代替。只保留最高階項去除最高項常數。

其他常見復雜度是：

f(n)=nlogn時，時間復雜度為O(nlogn)，可以稱為nlogn階。

f(n)=n³時，時間復雜度為O(n³)，可以稱為立方階。

f(n)=2ⁿ時，時間復雜度為O(2ⁿ)，可以稱為指數階。

f(n)=n!時，時間復雜度為O(n!)，可以稱為階乘階。

f(n)=(√n時，時間復雜度為O(√n)，可以稱為平方根階。