涓�銆?/p>
绠楁硶鐨勬椂闂村鏉傛�?/p>
T(n)
锛?/p>
鍒╃敤鏌愮畻娉曞鐞嗕竴涓棶棰樿妯′负
n
鐨勮緭
鍏ユ墍闇�瑕佺殑鏃堕棿銆?/p>
绌洪棿
锛?/p>
涓轰簡瑙ｆ眰闂鐨勫疄渚嬭�屾墽琛岀殑璁＄畻姝ラ鎵�闇�瑕侀鍐呭瓨绌洪棿
锛堟垨
瀛楋級鏁扮洰锛屼笉鍖呮嫭鐢ㄦ潵瀛樺偍杈撳叆鐨勭┖闂淬�?/p>
绠楁硶绌洪棿澶嶆潅鎬т笉鍙兘瓒呰繃
杩愯鏃堕棿鐨勫鏉傛�с�?/p>
鍏冭繍绠?/p>
:
瀵逛簬浠讳綍璁＄畻姝ラ锛屼笉绠¤緭鍏ユ暟鎹垨鎵ц鐨勭畻娉曪紝瀹冪殑浠ｄ环
鎬绘槸浠ヤ竴涓椂闂村父閲忎负涓婄晫锛?/p>
鍒欑О璇ヨ绠楁楠や负鍏冭繍绠椼�?/p>
鍩轰簬姣旇緝鐨?/p>
鎺掑簭闂鐨勬渶浼樼畻娉曪細
鎴戜滑閫氬父鎶婂湪
O(nlgn)
鏃堕棿鍐呯敤鍏冪礌姣旇緝娉曟帓
搴忕殑浠讳綍绠楁硶锛岀О涓哄熀浜庢瘮杈冪殑鎺掑簭闂鐨勬渶浼樼畻娉曘�備竴鑸潵璇达紝濡?/p>
鏋滃彲浠ヨ瘉鏄庝换浣曚竴涓眰瑙ｉ棶棰?/p>
A
鐨勭畻娉曞繀瀹氭槸惟
(f(n)),
閭ｄ箞鎴戜滑鎶婂湪
O(f(n))
鏃堕棿鍐呮眰瑙ｄ换浣曢棶棰?/p>
A
鐨勪换浣曠畻娉曢兘绉颁负闂
A
鐨勬渶浼樼畻娉曘�?/p>
绠楁硶璁捐鍘熷垯
:
姝ｇ‘鎬?/p>
纭畾鎬?/p>
娓呮櫚鎬с�?/p>
绠楁硶鐨勮绱?/p>
锛?/p>
1.
寰呰В闂鐨勬弿
杩?/p>
2.
绠楁硶璁捐鐨勪换鍔?/p>
3.
绠楁硶鍒嗘瀽銆?/p>
浜屻�?/p>
鍏崇郴杩愮畻
锛?/p>
鎸囩殑鏄敤浜庢楠屼袱涓嚑浣曞璞＄殑鐗瑰畾鐨勬嫇鎵戠┖闂村叧绯?/p>
鐨勯�昏緫鏂规硶銆?/p>
涓ゆ纭畾涓ゆ潯绾挎鏄惁鐩镐氦
锛?/p>
1.
蹇�熸帓鏂ュ疄楠岋紙鐭╁舰涓嶇浉浜わ級
2.
璺ㄧ珛
瀹?/p>
楠?/p>
锛?/p>
鍒?/p>
鏂?/p>
绾?/p>
娈?/p>
P1P2
鏄?/p>
鍚?/p>
鍜?/p>
Q1Q2
璺?/p>
绔?/p>
渚?/p>
鎹?/p>
鏄?/p>
锛?/p>
(P1-Q1)*(Q2-Q1)*(Q2-Q1)*(P2-Q1)>=0.
锛夊垽鏂?/p>
鐐规槸鍚﹀湪澶氳竟褰㈠唴
甯?/p>
鐢ㄧ畻娉曪細
1.
灏勭嚎娉?/p>
锛堝張鍙鍋舵祴璇曟硶锛?/p>
2.
杞娉曘�傜嚎娈靛湪澶氳竟褰㈠唴
鐨?/p>
涓�涓噸瑕佹潯浠舵槸绾挎鐨勪袱涓鐐归兘鍦ㄥ杈瑰舰鍐咃紝
绗簩涓繀瑕佹潯浠舵槸绾?/p>
娈靛拰澶氳竟褰㈢殑鎵�鏈夎竟閮戒笉鍐呬氦銆?/p>
绾挎鍦ㄥ杈瑰舰鍐呭垽鏂楠?/p>
锛?/p>
1.
鍏堟眰鍑?/p>
鎵�鏈夊拰绾挎鐩镐氦鐨勫杈瑰舰鐨勯《鐐?/p>
2.
鐒跺悗鎸夌収
X-Y
鍧愭爣鎺掑簭锛?/p>
X
鍧愭爣