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怎麼計算
如果a的x次方等於N（a>0，且a不等於1），那麼數x叫做以a為底N的對數（logarithm），記作x=logaN。其中，a叫做對數的底數，N叫做真數。
計算方式：
根據2^3=8，可得log2 8=3。
(2)logn的演算法擴展閱讀：
推導公式
log(1/a)(1/b)=log(a^-1)(b^-1)=-1logab/-1=loga(b)
loga(b)*logb(a)=1
loge(x)=ln(x)
lg(x)=log10(x)
求導數
(xlogax)'=logax+1/lna
其中，logax中的a為底數，x為真數；
(logax)'=1/xlna
特殊的即a=e時有
(logex)'=(lnx)'=1/x[4]
C. 時間復雜度log怎麼算
如果程序運行的規模，每執行一次的規模是按等比例規模降低的，那麼這個演算法的時間復雜度就是logn的。
D. 幾個數學證明題，關於log的計算，求解答，高分懸賞
你就記住一點，任何大於0的n 取了log之後，就再也無法和之前的自己n平起平坐，哪怕是n的delta次方，delta特別小。因為考慮從f(n) = n^a - logn 求導得f『(n) = a*n^(a-1)-1/n = (a*n^a - 1)/n 所以當n很大很大的時候a*n^a 一定是大於1的，所以導函數大於0，函數遞增到沒有盡頭，從而n^a 把 logn 遠遠甩在身後。
所以(a) 兩邊取log得到 logn平方 vs n*loglogn 有n的完勝，右贏
(b) klogn vs logn的k次方 這個很顯然k是0或是負，都是klogn負 ，logn的k次方正，沒得比；
其次兩邊取log變成logk + loglogn vs k*loglogn 所以當k在0,1之間，左贏；k=1，打平；k>1 右贏
(c) (logn)!是個啥。。暫且當logn後取整數部分。 網路一下stirling公式，換成等價形式兩邊取log
變成logn * logloglogn vs ... 總之右邊有n，右邊完勝。
(d) 還是stirling，n^n vs sqrt(2*pi*n)/exp(n) * n^n 這個sqrt(2*pi*n)/exp(n) 顯然比1要小，左勝
E. 數學中的logn是怎麼回事來著哪位數學大神解釋一下，工作好多年這些東西忘光了
log是對數函數
[1]對數的定義：一般地，如果ax=N（a>0，且a≠1），那麼數x叫做以a為底N的對數，記作x=logaN，讀作以a為底N的對數，其中a叫做對數的底數，N叫做真數。對數函數：一般地，函數y=logax（a>0，且a≠1）叫做對數函數，也就是說以冪為自變數，指數為因變數，底數為常量的函數，叫對數函數。其中x是自變數，函數的定義域是（0，+∞）。它實際上就是指數函數的反函數，可表示為x=ay。因此指數函數里對於a的規定，同樣適用於對數函數。「log」是拉丁文logarithm（對數）的縮寫，讀作：[英][lɔɡ][美][lɔɡ, lɑɡ]。求採納 謝謝F. 演算法時間復雜度比較：根號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)演算法，只有大數據才會用米勒羅賓
G. 關於log的公式
當a>0且a≠1時，M>0,N>0，那麼：
（1）log(a)(MN)=log(a)(M)+log(a)(N);
（2）log(a)(M/N)=log(a)(M)-log(a)(N);
（3）log(a)(M^n)=nlog(a)(M) （n∈R）
(4)log(a^n)(M)=1/nlog(a)(M)(n∈R)
（5）換底公式：log(A)M=log(b)M/log(b)A (b>0且b≠1）
(6)a^(log(b)n)=n^(log(b)a) 證明： 設a=n^x則a^(log(b)n)=（n^x）^log(b)n=n^（x·log(b)n）=n^log(b)（n^x）=n^(log(b)a)
(7)對數恆等式：a^log（a)N=N; log（a）a^b=b
（8）由冪的對數的運算性質可得(推導公式)
1.log(a)M^(1/n)=(1/n)log(a)M , log(a)M^(-1/n)=(-1/n)log(a)M
2.log(a)M^(m/n)=(m/n)log(a)M , log(a)M^(-m/n)=(-m/n)log(a)M
3.log(a^n)M^n=log(a)M , log(a^n)M^m=(m/n)log(a)M
4.log(以 n次根號下的a 為底)(以 n次根號下的M 為真數)=log(a)M , log(以 n次根號下的a 為底)(以 m次根號下的M 為真數)=(n/m)log(a)M
5.log(a)b×log(b)c×log(c)a=1
H. 最近在研究演算法，書上一直說時間是O（logn），但是沒有明確說logn的底是什麼，這樣理解是否准確
從理論上，無論低是什麼都無關緊要，因為不同底的logn之間只存在常數倍的關系，這與n無關，不會影響復雜度的大小。
I. 1+3.23logN怎麼算來的
log即以10為底的對數
如N=50，則log50=log（100/2）=log100-log2=2-log2=2-0.301=1.699
1+3.23log50=1+3.23×1.699=6.48777
若N=100，則1+3.23log100=1+3.23×2=7.46
J. 最近在研究演算法，書上一直說時間是O（logn），但是沒有明確說logn的底是什麼，所以請教一下，謝謝
從我的理解上來說，我們先考慮O(logx(n))和O(logy(n))，x!=y，我們是在考慮n趨於無窮的情況。
求當n趨於無窮大時logx(n)/logy(n)的極限可以發現，極限等於lny/lnx（用一次洛必達可求得），也就是一個常數，也就是說，在n趨於無窮大的時候，這兩個東西僅差一個常數。
所以從研究演算法的角度log的底數不重要。
最後，結合上面，我來說一下關於大O的定義（我使用的是演算法導論28頁的定義），注意把這個定義和高等數學中的極限部分做比較，我們顯然可以發現，這里的定義正是體現了一個極限的思想，假設我們將n0取一個非常大的數字，顯然，當n大於n0的時候，我們可以發現任意底數的一個對數函數其實都相差一個常數倍而已。所以書上說寫的O（logn）已經可以表達所有底數的對數了，就像O(n^2)一樣。
沒有非常嚴格的證明，不過我覺得這樣說比較好理解，如果你有興趣證明，完全可以參照高數上對極限趨於無窮的證明，希望你能理解。