復雜度為o的計算方法

『壹』 演算法的時間復雜度O（n）到底怎麼算

看循環或者遞歸的層數。

比如該函數為O（n）

intf(intx,inty)
{
inti,j;
for(i=0;i<x;i++)printf("%d
",y);
}

而該函數為O（n2）

intf(intx,inty)
{
inti,j;
for(i=0;i<x;i++)for(j=0;j<y;j++)printf("%d
",y);
}

『貳』 歸並排序的時間復雜度O是怎麼算出來的呢

歸並排序每次會把當前的序列一分為二，然後兩部分各自排好序之後再合並，這樣的話你可以手動模擬出一顆二叉樹來，每一層的總計算量是O(n)的，總的層數是O(logn)的，所以總的復雜度是nlogn

『叄』 數據結構中演算法空間復雜度怎麼算

數據結構中演算法空間復雜度計算方法：

一個演算法的空間復雜度只考慮在運行過程中為局部變數分配的存儲空間的大小，它包括為參數表中形參變數分配的存儲空間和為在函數體中定義的局部變數分配的存儲空間兩個部分。

若一個演算法為遞歸演算法，其空間復雜度為遞歸所使用的堆棧空間的大小，它等於一次調用所分配的臨時存儲空間的大小乘以被調用的次數(即為遞歸調用的次數加1，這個1表示開始進行的一次非遞歸調用)。

演算法的空間復雜度一般也以數量級的形式給出。如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)；當一個演算法的空間復雜度與以2為底的n的對數成正比時，可表示為O(log2n)；當一個演算法的空間復雜度與n成線性比例關系時，可表示為O(n)。若形參為數組，則只需要為它分配一個存儲由實參傳送來的一個地址指針的空間，即一個機器字長空間；若形參為引用方式，則也只需要為其分配存儲一個地址的空間，用它來存儲對應實參變數的地址，以便由系統自動引用實參變數。

(3)復雜度為o的計算方法擴展閱讀：

空間復雜度(Space Complexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時間復雜度是O(n^2),空間復雜度是O(1) 。而一般的遞歸演算法就要有O(n)的空間復雜度了，因為每次遞歸都要存儲返回信息。一個演算法的優劣主要從演算法的執行時間和所需要佔用的存儲空間兩個方面衡量。

個演算法的空間復雜度S(n)定義為該演算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。空間復雜度(SpaceComplexity)是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。一個演算法在計算機存儲器上所佔用的存儲空間，包括存儲演算法本身所佔用的存儲空間，演算法的輸入輸出數據所佔用的存儲空間和演算法在運行過程中臨時佔用的存儲空間這三個方面。

『肆』 數組排序的最少時間復雜度O(nlog2n)怎麼計算的

for(int j=1; j<=n; j*=2)

這個循環最終執行的次數假設為x，則x次的時候j=2^x 。

當j>n時停止執行，於是2^x>n ，則可以認為該循環一共執行了log2(n)次。

所以該循環的時間復雜度為o(log2(n))，簡記為o(log n) ，忽略掉2的底數。

『伍』 如何計算時間復雜度

1、先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出T（n）的同數量級（它的同數量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若T(n)/f(n)求極限可得到一常數c，則時間復雜度T（n）=O（f（n））。

2、舉例

for（i=1;i<=n;++i）

{for(j=1;j<=n;++j)

{c[ i ][ j ]=0; //該步驟屬於基本操作 執行次數：n的平方次

for(k=1;k<=n;++k)

c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬於基本操作 執行次數：n的三次方次}}

則有 T（n）= n的平方+n的三次方，根據上面括弧里的同數量級，我們可以確定 n的三次方為T（n）的同數量級

則有f（n）= n的三次方，然後根據T（n）/f（n）求極限可得到常數c

則該演算法的 時間復雜度：T（n）=O（n的三次方）

),線性階O(n),線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

關於對其的理解

《數據結構（C語言版）》 ------嚴蔚敏 吳偉民編著 第15頁有句話「整個演算法的執行時間與基本操作重復執行的次數成正比。」

基本操作重復執行的次數是問題規模n的某個函數f(n)，於是演算法的時間量度可以記為：T(n) = O(f(n))

如果按照這么推斷，T(n)應該表示的是演算法的時間量度，也就是演算法執行的時間。

而該頁對「語句頻度」也有定義：指的是該語句重復執行的次數。

如果是基本操作所在語句重復執行的次數，那麼就該是f(n)。

上邊的n都表示的問題規模。

『陸』 時間復雜度o(nlogn)的演算法是什麼

時間復雜度o(nlogn)的演算法是採用「分治思想」，將要排序的數組從中間分成前後兩個部分，然後對前後兩個部分分別進行排序，再將排序好的兩部分合並在一起，這樣數組就有序。

每次劃分區域都選擇中間點進行劃分，所以遞歸公式可以寫成：T(n) = T(n/2) + T(n/2) + n， T(1) = C(常數) //每次合並都要調用Merge()函數，時間復雜度為O(n)，等價T(n) = 2kT(n/2k) + k * n， 遞歸的最終狀態為T(1)即n/2k = 1，所以k = log2n。

原理分析：

1、運用了分治的思想。選取分區值，將待排序列分為兩個前後兩部分，前部分數據元素的值小於等於分區值，後部分的數據元素的值大於等於分區值；繼續對前後兩部分分別進行分區，直到分區大小為1。

2、交換操作的執行次數可以由時間復雜度分析過程得出，Merge()中總的交換次數為n * logn，因為不管兩個子序列的大小，子序列中的各個元素都會先放入臨時數組temp中，再重新放回原序列；比較操作的次數小於等於交換操作次數，最大交換次數為n * logn。

『柒』 演算法的時間復雜度O到底怎麼算

是說明一個程序根據其數據n的規模大小所使用的大致時間和空間說白了就是表示如果隨著n的增長時間或空間會以什麼樣的方式進行增長例for(inti=0;i