int main() {
int a[10]={1,3,4,5,6,13,15,16,18,19};
int b[5]={2,6,7,8,10};
int a_len=sizeof(a)/4;
int b_len=sizeof(b)/4;
int c[a_len+b_len];
printf("陣列長度\n");
printf("%d %d\n",a_len,b_len);
//并序
int i=0;
int l=0;
int z=0;
for (z = 0; z<2*b_len ;z++ )
{
if (a[i] > b[l])
{
c[z] = b[l];
l++;
}else if (a[i] <= b[l])
{
c[z] = a[i];
i++;
}
}
//無需合并的部分
for (int x=2*b_len,p=b_len; x<(a_len+b_len) ; x++,p++)
{
c[x]=a[p];
}
//并序之后輸出
printf("并序之后輸出:\n");
for (int y = 0; y < (a_len+b_len); y++)
{
printf(" %d ",c[y]);
}
return 0;
}
uj5u.com熱心網友回復：
最大n+m回圈，3次for也就3*(n+m)，所以還是O(n)級別的，因為演算法只關注n的幾次冪，不關心系數的影響，所以時間復雜度是O(n)或者O(n+m)uj5u.com熱心網友回復：
復雜度就要看執行的次數和資料長度之間的關系是什么對于這個題目來說，二路歸并，對于兩個已經排序好的陣列，合并成為一個，那么資料長度就是兩個陣列的和為N
要計算最復雜的情況，兩個陣列一樣長， 交叉進入，這是比較次數最多的時候，但是也就是最多比較N-1次
N-1是關于N的一次函式， 結果就是O（N）
哪怕是10000N+1000000次計算， 復雜度都是O（N）
如果是aN^m + bN^(m-1) + ... 這種多項式， 那么就是O（N^m） 只取冪最大的
如果是2^N + .... 這種， 就是O（2^N）
總之就是取對結果影響最大的系數來
uj5u.com熱心網友回復：
這里的N其實和具體的陣列長度一毛錢關系都沒有都是在假定N是很大，大到足以忽略其他的資料的影響到情況下來估算的
這也是為什么，計算量是 0.0001N + 100000000 的時候， 也是O（N）復雜的原因
這里評估的是演算法， 演算法本身就是要適應任意長度的陣列的， 這樣才有意義
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/125649.html
標籤：C++ 語言
上一篇：51單片機
下一篇：超級簡單問題求助