演算法實際時間復雜度例題

1. 演算法題時間復雜度問題

在演算法題中調用內置函數應該考慮把這個函數算入總復雜度中的。調用內置函數，與調用自定義函數的實質是一樣的。如果在一個本身時間復雜度為O(n)在演算法中調用了一個時間復雜度為O(logn)的內置函數，那麼，整個演算法的時間復雜度就是O(nlogn)

2. 演算法的時間復雜度計算問題

第一題:
int
i=1,k=100這條語句演算法步數是2步，執行頻率是1;
循環中，
k=k+1;這條語句每次演算法步數是1;執行頻率是n/2-1;
i+=2這條語句每次演算法步數是1;執行頻率是n/2-1;
所以演算法復雜度為1*(n/2-1)+1*(n/2-1)+2=n=o(n);

3. 演算法時間復雜度x=2 while(x<n/2) x=2*x 求演算法時間復雜度

演算法時間復雜度為：O（log₂n）。

演算法復雜度是指演算法在編寫成可執行程序後，運行時所需要的資源，資源包括時間資源和內存資源。應用於數學和計算機導論。與時間復雜度類似，空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。記作：S（n）＝O（f（n））。

演算法執行期間所需要的存儲空間包括3個部分：演算法程序所佔的空間；輸入的初始數據所佔的存儲空間；演算法執行過程中所需要的額外空間。在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術。

4. 演算法設計題:計算時間復雜度

關於時間復雜度的計算是按照運算次數來進行的，比如1題：
sum1(intn)
{intp=1,sum=0,m;//1次
for(m=1;m<=n;m++)//n+1次
{p*=m;//n次
sum+=p;}//n次
return(sum);//1次
}
最後總的次數為
1+（n+1）+n+n+1+1=3n+3
所以時間復雜度f（o）=n；（時間復雜度只管n的最高次方，不管他的系數和表達式中的常量）
其餘的一樣，不明白的可以來問我

5. 演算法時間復雜度問題，題目如下，謝謝！

樓主你好
大致是這樣:
首先說:
for(i=1;i<=n;i*=2)
語句;
這個的循環的執行的次數
是:
og2 (n-1 +1)
log以2為底 n的對數 + 1

那麼把 i=1換做j j是從1~n-1 因為 當j為n時函數結束

因此運行的次數就是：
j:1~n-1
(log2 (n-j+1))+1 的和
就是:
log2 (n!) +n

希望能幫助你哈

6. 分析下列演算法的時間復雜度。麻煩也告訴一下怎樣算的，謝謝！

每當調用這個函數時會產生2個遞歸分支，所以時間復雜度是O(2^n)。
n==1時，調用1次rec(1)，
n==2時，調用1次rec(2)，2次rec(1)，
n==3時，調用1次rec(3)，2次rec(2)，4次rec(1)，
以此類推，總的調用次數為2^0+2^1+2^2+...+2^(n-1)=2^n-1，
因為函數內不存在循環，T(n)=(2^n-1)*1=2^n-1，
存在正的常數c,n0使得對於任意n>=n0時有T(n)<=c*2^n，
所以這個時間復雜度是O(2^n)。

7. 演算法時間復雜度的計算例題

第一題：
int i=1,k=100這條語句演算法步數是2步,執行頻率是1；
循環中, k=k+1;這條語句每次演算法步數是1；執行頻率是n/2-1; i+=2這條語句每次演算法步數是1；執行頻率是n/2-1;
所以演算法復雜度為1*（n/2-1）+1*（n/2-1）+2=n=o(n);