演算法復雜度logn

A. 嚴蔚敏老師的《數據結構》里，關於時間復雜度的寫法，譬如logn，這個對數函數的底數是多少啊

演算法中log級別的時間復雜度都是由於使用了分治思想,這個底數直接由分治的復雜度決定。如果採用二分法,那麼就會以2為底數,三分法就會以3為底數,其他亦然。不過無論底數是什麼,log級別的漸進意義是一樣的。也就是說該演算法的時間復雜度的增長與處理數據多少的增長的關系是一樣的。

(1)演算法復雜度logn擴展閱讀：

時間復雜度的計算方法

（1）一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得T(n)/f(n)的極限值（當n趨近於無窮大時）為不等於零的常數，則稱f(n)是T(n)的同數量級函數。

記作T(n)=O(f(n))，稱O(f(n))
為演算法的漸進時間復雜度，簡稱時間復雜度。

（2）在計算時間復雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出 T(n) 的同數量級。

（3）在pascal中比較容易理解，容易計算的方法是：看看有幾重for循環，只有一重則時間復雜度為O(n)，二重則為O(n^2)，依此類推，如果有二分則為O(logn)，二分例如快速冪、二分查找，如果一個for循環套一個二分，那麼時間復雜度則為O(nlogn)。

B. 時間復雜度log怎麼算

如果程序運行的規模，每執行一次的規模是按等比例規模降低的，那麼這個演算法的時間復雜度就是logn的。

C. 演算法時間復雜度比較：根號n與logn相比哪個更優優多少試根據下圖猜想其演算法

米勒羅賓是logn的演算法，但是實際應用上它並不穩定，一般在范圍較大（int64范圍）才會用，一般的情況用的都是sqrt(n)的演算法，但是在需要判斷大量素數的情況下（假設判斷次數為m），一般是比較m*sqrt(n)和n的大小，如果前者小就暴力判斷，否則用篩法會更快。

然後比較，在不考慮常數的情況下是logn更優，但是演算法常數導致在數據較小的一些情況下sqrt(n)反而更快。

第一個根號n的：

#include<cmath>

inlineboolisPrime(intx){
if(x==2){returntrue;}
if(x<2){returnfalse;}
intpos=int(sqrt(x))+1;
for(inti=2;i<=pos;++i){
if(x%i==0){returnfalse;}
}
returntrue;
}

然後logn的米勒羅賓你可以看下博客網頁鏈接

然後提供一個篩法的代碼（stl版本）

#include<vector>

boolvis[MAXNUM];//MAXNUM就是最大數字
std::vector<int>primes;//儲存素數

inlinevoidgetPrimes(intmaxn){
for(inti=2;i<=maxn;++i){
if(!vis[i]){primes.push_back(i);}
for(size_tj=0;j<primes.size()&&primes[j]*i<=maxn;++j){
vis[primes[j]*i]=true;
}
}
}

實際應用一般用篩法或者sqrt(n)演算法，只有大數據才會用米勒羅賓

D. 電腦編程中快速排序的時間復雜度n log n 是n*log(n)還是什麼

復雜度的表示式裡面只看冪級不看具體底數，log n跟log2n是一回事，感覺你有些概念不清的樣子，時間復雜度的n就表示演算法處理的數字個數，快速排序的時間復雜度就是n log n，快速排序10個數的時間復雜度也還是n log n，你可以說n=10，但是時間復雜度的表示式裡面要求把具體的輸入個數用n表示，因為這樣才能反映出演算法在輸入個數增加的時候運行時間相應增加的程度，也就是「時間復雜度」這個概念本身想說明的問題。