时间复杂度(计算方法,如果计算,及其解释) 时间复杂度的计算。
\u5173\u4e8e\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u6211\u4e0d\u61c2\u4ed6\u7684\u8ba1\u7b97\u516c\u5f0f\u3002\u5d4c\u5957\u5faa\u73af\uff0c\u4f8b\u5982
for i:=1 to n do
for j:=1 to n do
\u5bf9\u4e8ei=1,2,3...n\u4e2d\u7684\u6bcf\u4e00\u4e2a\u503c\uff0cj\u90fd\u4ece1\u904d\u5386\u5230\u4e86n\uff0c\u6240\u4ee5\u4e00\u5171\u8fd0\u884c\u4e86 n*n\u6b21
1.\u65f6\u95f4\u590d\u6742\u5ea6O(n^2)
2.\u65f6\u95f4\u590d\u6742\u5ea6O(n^2)
3.\u65f6\u95f4\u590d\u6742\u5ea6O(n^2)
4.\u65f6\u95f4\u590d\u6742\u5ea6O(n)
5.\u65f6\u95f4\u590d\u6742\u5ea6O(n^3)
\u4e00\u822c\u6765\u8bf4\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662f\u603b\u8fd0\u7b97\u6b21\u6570\u8868\u8fbe\u5f0f\u4e2d\u53d7n\u7684\u53d8\u5316\u5f71\u54cd\u6700\u5927\u7684\u90a3\u4e00\u9879(\u4e0d\u542b\u7cfb\u6570)
\u6bd4\u5982\uff1a\u4e00\u822c\u603b\u8fd0\u7b97\u6b21\u6570\u8868\u8fbe\u5f0f\u7c7b\u4f3c\u4e8e\u8fd9\u6837\uff1a
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a0\u65f6\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(2^n);
a=0,b0 =>O(n^3);
a,b=0,c0 =>O(n^2)\u4f9d\u6b64\u7c7b\u63a8
\u90a3\u4e48\uff0c\u603b\u8fd0\u7b97\u6b21\u6570\u53c8\u662f\u5982\u4f55\u8ba1\u7b97\u51fa\u7684\u5462\uff1f
\u4e00\u822c\u6765\u8bf4\uff0c\u6211\u4eec\u7ecf\u5e38\u4f7f\u7528for\u5faa\u73af\uff0c\u5c31\u50cf\u521a\u624d\u4e94\u4e2a\u9898\uff0c\u6211\u4eec\u5c31\u4ee5\u5b83\u4eec\u4e3a\u4f8b
1.\u5faa\u73af\u4e86n*n\u6b21\uff0c\u5f53\u7136\u662fO(n^2)
2.\u5faa\u73af\u4e86(n+n-1+n-2+...+1)\u2248(n^2)/2\uff0c\u56e0\u4e3a\u65f6\u95f4\u590d\u6742\u5ea6\u662f\u4e0d\u8003\u8651\u7cfb\u6570\u7684\uff0c\u6240\u4ee5\u4e5f\u662fO(n^2)
3.\u5faa\u73af\u4e86(1+2+3+...+n)\u2248(n^2)/2,\u5f53\u7136\u4e5f\u662fO(n^2)
4.\u5faa\u73af\u4e86n-1\u2248n\u6b21\uff0c\u6240\u4ee5\u662fO(n)
5.\u5faa\u73af\u4e86(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(\u8fd9\u4e2a\u516c\u5f0f\u8981\u8bb0\u4f4f\u54e6)\u2248(n^3)/3\uff0c\u4e0d\u8003\u8651\u7cfb\u6570\uff0c\u81ea\u7136\u662fO(n^3)
\u53e6\u5916\uff0c\u5728\u65f6\u95f4\u590d\u6742\u5ea6\u4e2d\uff0clog(2,n)(\u4ee52\u4e3a\u5e95)\u4e0elg(n)(\u4ee510\u4e3a\u5e95)\u662f\u7b49\u4ef7\u7684\uff0c\u56e0\u4e3a\u5bf9\u6570\u6362\u5e95\u516c\u5f0f\uff1a
log(a,b)=log(c,b)/log(c,a)
\u6240\u4ee5\uff0clog(2,n)=log(2,10)*lg(n),\u5ffd\u7565\u6389\u7cfb\u6570\uff0c\u4e8c\u8005\u5f53\u7136\u662f\u7b49\u4ef7\u7684
\u5982\u679c\u8fd8\u4e0d\u660e\u767d\u5c31\u5728QQ\u4e0a\u8bf4\u5427\uff0c786453572
作用： 时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。
2. 一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））
分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。
3. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，在找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））
例：算法：
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的三次方）
绛旓細闂鍏細浜鸿劯璇嗗埆鐨璁＄畻鏃堕棿澶嶆潅搴鎬庝箞绠 閫掑綊绠楁硶鐨勬椂闂村鏉傚害鍒嗘瀽 鏀惰棌 鍦ㄧ畻娉曞垎鏋愪腑锛屽綋涓涓畻娉曚腑鍖呭惈閫掑綊璋冪敤鏃讹紝鍏舵椂闂村鏉傚害鐨勫垎鏋愪細杞寲涓轰竴涓掑綊鏂圭▼姹傝В銆傚疄闄呬笂锛岃繖涓棶棰樻槸鏁板涓婃眰瑙ｆ笎杩戦樁鐨勯棶棰橈紝鑰岄掑綊鏂圭▼鐨勫舰寮忓绉嶅鏍凤紝鍏舵眰瑙鏂规硶涔熸槸涓嶄竴鑰岃冻锛屾瘮杈冨父鐢ㄧ殑鏈変互涓嬪洓绉嶆柟娉曪細 (1)浠ｅ叆...
绛旓細杩欑鐢ㄤ釜澶у啓鐨 O 鏉ヤ唬琛ㄧ畻娉曠殑鏃堕棿澶嶆潅搴︾殑璁版硶鏈変釜涓撲笟鐨勫悕瀛楀彨鈥滃ぇO闃垛濊娉曘傞偅涔堥氳繃瀵逛笂杩扮殑渚嬪瓙杩涜鎬荤粨锛屾垜浠粰鍑虹畻娉曠殑鏃堕棿澶嶆潅搴︼紙澶闃讹級鐨璁＄畻鏂规硶銆傛帹瀵尖滃ぇO闃垛濈殑姝ラ锛1銆佺敤甯告暟 1 鍙栦唬杩愯鏃堕棿涓殑鎵鏈夊姞娉曞父鏁般2銆佸湪淇敼鍚庣殑杩愯娆℃暟鍑芥暟涓紝鍙繚鐣欐渶楂橀樁椤广3銆濡傛灉鏈楂橀樁...
绛旓細濡備綍璁＄畻鏃堕棿澶嶆潅搴 瀹氫箟锛濡傛灉涓涓棶棰樼殑瑙勬ā鏄痭锛岃В杩欎竴闂鐨勬煇涓绠楁硶鎵闇瑕佺殑鏃堕棿涓篢(n)锛屽畠鏄痭鐨勬煇涓鍑芥暟 T(n)绉颁负杩欎竴绠楁硶鐨勨滄椂闂村鏉傛р濄傚綋杈撳叆閲弉閫愭笎鍔犲ぇ鏃讹紝鏃堕棿澶嶆潅鎬х殑鏋侀檺鎯呭舰绉颁负绠楁硶鐨勨滄笎杩戞椂闂村鏉傛р濄傛垜浠父鐢ㄥぇO琛ㄧず娉曡〃绀鏃堕棿澶嶆潅鎬э紝娉ㄦ剰瀹冩槸鏌愪竴涓畻娉曠殑鏃堕棿澶嶆潅鎬с
绛旓細O锛1锛夌殑绠楁硶闇瑕1绉掓墽琛屽畬姣曘侽锛坣锛夌殑绠楁硶闇瑕10锛000绉 鈮 2.7灏忔椂 鎵ц瀹屾瘯銆侽锛坣2锛夌殑绠楁硶闇瑕100锛000锛000绉 鈮 3.17骞 鎵ц瀹屾瘯銆侽锛坣锛侊級鐨勭畻娉曢渶瑕乆XXXXXXX(绯荤粺鐨璁＄畻鍣ㄥ凡缁忕畻涓嶅嚭鏉ヤ簡)銆傚彲瑙佺畻娉曠殑鏃堕棿澶嶆潅搴褰卞搷鏈夊澶с傛墍浠锛1锛夊拰O锛坣锛夊樊浜2.7灏忔椂锛屽尯鍒樉鑰屾槗瑙併
绛旓細2銆佺┖闂村鏉傚害 绠楁硶鐨勭┖闂村鏉傚害鏄寚绠楁硶闇瑕佹秷鑰楃殑鍐呭瓨绌洪棿銆傚叾璁＄畻鍜岃〃绀鏂规硶涓鏃堕棿澶嶆潅搴绫讳技锛屼竴鑸兘鐢ㄥ鏉傚害鐨勬笎杩戞ф潵琛ㄧず銆傚悓鏃堕棿澶嶆潅搴︾浉姣旓紝绌洪棿澶嶆潅搴︾殑鍒嗘瀽瑕佺畝鍗曞緱澶氥3銆佹纭 绠楁硶鐨勬纭ф槸璇勪环涓涓畻娉曚紭鍔ｇ殑鏈閲嶈鐨勬爣鍑嗐4銆佸彲璇绘 绠楁硶鐨勫彲璇绘ф槸鎸囦竴涓畻娉曞彲渚涗汉浠槄璇荤殑瀹规槗绋嬪害...
绛旓細璁＄畻鏃堕棿澶嶆潅搴鏃讹紝闇瑕佽冭檻绠楁硶涓瘡涓搷浣滅殑鎵ц娆℃暟锛屽苟灏嗗叾琛ㄧず涓鸿緭鍏ヨ妯＄殑鍑芥暟銆傜劧鍚庯紝鎵惧埌鍑芥暟涓殑鏈楂樻椤癸紝蹇界暐浣庢椤瑰拰甯告暟绯绘暟锛屽緱鍒版椂闂村鏉傚害銆備緥濡锛屽鏋绠楁硶涓殑寰幆鎵цn娆★紝鍒欐椂闂村鏉傚害涓篛(n)銆傞氳繃璁＄畻鏃堕棿澶嶆潅搴︼紝鍙互姣旇緝涓嶅悓绠楁硶鐨勬晥鐜囷紝骞堕夋嫨鏈浼樼畻娉曘
绛旓細姹傝В绠楁硶鐨鏃堕棿澶嶆潅搴鐨勫叿浣撴楠ゆ槸锛氣懘鎵惧嚭绠楁硶涓殑鍩烘湰璇彞锛涚畻娉曚腑鎵ц娆℃暟鏈澶氱殑閭ｆ潯璇彞灏辨槸鍩烘湰璇彞锛岄氬父鏄渶鍐呭眰寰幆鐨勫惊鐜綋銆傗懙璁＄畻鍩烘湰璇彞鐨勬墽琛屾鏁扮殑鏁伴噺绾э紱鍙渶璁＄畻鍩烘湰璇彞鎵ц娆℃暟鐨勬暟閲忕骇锛岃繖灏辨剰鍛崇潃鍙淇濊瘉鍩烘湰璇彞鎵ц娆℃暟鐨勫嚱鏁颁腑鐨勬渶楂樻骞傛纭嵆鍙紝鍙互蹇界暐鎵鏈変綆娆″箓鍜屾渶楂樻骞...
绛旓細姹傝В绠楁硶鐨鏃堕棿澶嶆潅搴鐨勫叿浣撴楠ゆ槸锛1銆佹壘鍑虹畻娉曚腑鐨勫熀鏈鍙ワ細绠楁硶涓墽琛屾鏁版渶澶氱殑閭ｆ潯璇彞灏辨槸鍩烘湰璇彞锛岄氬父鏄渶鍐呭眰寰幆鐨勫惊鐜綋銆2銆璁＄畻鍩烘湰璇彞鐨勬墽琛屾鏁扮殑鏁伴噺绾э細锛1锛夊彧闇璁＄畻鍩烘湰璇彞鎵ц娆℃暟鐨勬暟閲忕骇锛岃繖灏辨剰鍛崇潃鍙淇濊瘉鍩烘湰璇彞鎵ц娆℃暟鐨勫嚱鏁颁腑鐨勬渶楂樻骞傛纭嵆鍙紝鍙互蹇界暐鎵鏈変綆娆″箓鍜...
绛旓細鍩烘湰鎿嶄綔鏄祴鍊兼搷浣滃拰寰幆鍐呯殑鍔犳硶鎿嶄綔銆# 寰幆杩唬浜唍娆★紝鍏朵腑n鏄緭鍏ユ暟缁刟rr鐨勯暱搴︺# 鍥犳锛屾绘搷浣滄鏁颁负n娆°# 鏃堕棿澶嶆潅搴涓篛(n)銆傝繖鍙槸涓涓畝鍗曠殑绀轰緥锛屽鏉傜殑绠楁硶鍙兘娑夊強鏇村鐨勬帶鍒剁粨鏋勫拰宓屽寰幆锛岄渶瑕佹洿璇︾粏鐨勫垎鏋愩備絾鏄紝杩欎釜鍩烘湰鐨鏂规硶鍙互甯姪浣犲紑濮璁＄畻绠楁硶鐨勬椂闂村鏉傚害銆
绛旓細1銆鏃堕棿澶嶆潅搴鏄寚鎵ц绠楁硶鎵闇瑕佺殑璁＄畻宸ヤ綔閲忋傛椂闂村鏉傚害鏄竴涓嚱鏁帮紝瀹冨畾鎬ф弿杩颁簡璇ョ畻娉曠殑杩愯鏃堕棿銆傝繖鏄竴涓叧浜庝唬琛ㄧ畻娉曡緭鍏ュ肩殑瀛楃涓茬殑闀垮害鐨勫嚱鏁般傛椂闂村鏉傚害甯哥敤澶绗﹀彿琛ㄨ堪锛屼笉鍖呮嫭杩欎釜鍑芥暟鐨勪綆闃堕」鍜岄椤圭郴鏁般2銆佺┖闂村鏉傚害鏄寚鎵ц杩欎釜绠楁硶鎵闇瑕佺殑鍐呭瓨绌洪棿銆傜┖闂村鏉傚害闇瑕佽冭檻鍦ㄨ繍琛岃繃绋嬩腑...
