鍗佸ぇ缁忓吀鎺掑簭绠楁硶
https://www.cnblogs.com/onepixel/p/7674659.html
蹇熸帓搴忎唬鐮佺ず渚
https://shimo.im/docs/98KjvGwwGpTpYGKy/
褰掑苟鎺掑簭浠ｇ爜绀轰緥
https://shimo.im/docs/YqgG6vtdKwkXJkWx/
鍫嗘帓搴忎唬鐮佺ず渚
https://shimo.im/docs/6kRVHRphpgjHgCtx/
| 鎺掑簭鏂规硶 | 鏃堕棿澶嶆潅搴(骞冲潎) | 鏃堕棿澶嶆潅搴(鏈鍧) | 鏃堕棿澶嶆潅搴(鏈濂) | 绌洪棿澶嶆潅搴 | 绋冲畾鎬 |
|---|---|---|---|---|---|
| 鎻掑叆鎺掑簭 | O(n^2) | O(n^2) | O(n) | O(1) | 绋冲畾 |
| 甯屽皵鎺掑簭 | O(n^1.3) | O(n^2) | O(n) | O(1) | 涓嶇ǔ瀹 |
| 閫夋嫨鎺掑簭 | O(n^2) | O(n^2) | O(n^2) | O(1) | 涓嶇ǔ瀹 |
| 鍫嗘帓搴 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 涓嶇ǔ瀹 |
| 鍐掓场鎺掑簭 | O(n^2) | O(n^2) | O(n) | O(1) | 绋冲畾 |
| 蹇熸帓搴 | O(nlog2n) | O(n^2) | O(nlog2n) | O(nlog2n) | 涓嶇ǔ瀹 |
| 褰掑苟鎺掑簭 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 绋冲畾 |
| 璁℃暟鎺掑簭 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 绋冲畾 |
| 妗舵帓搴 | O(n+k) | O(n^2) | O(n) | O(n+k) | 绋冲畾 |
| 鍩烘暟鎺掑簭 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 绋冲畾 |
log2n 鐨勬帓搴忔柟娉曢渶瑕侀噸鐐规帉鎻
蹇燂紝褰掑苟鎺掑簭鐢ㄥ埌浜嗗垎娌荤殑鎬濇兂銆
姣忔鎵炬渶灏忓,鐒跺悗鏀惧埌寰呮帓搴忔暟缁勭殑璧峰浣嶇疆銆
浠庡墠鍒板悗閫愭鏋勫缓鏈夊簭搴忓垪;瀵逛簬鏈帓搴忔暟鎹紝鍦ㄥ凡鎺掑簭搴忓垪涓粠鍚庡悜鍓嶆壂鎻忥紝鎵惧埌鐩稿簲浣嶇疆骞舵彃鍏ャ
宓屽寰幆锛屾瘡娆℃煡鐪嬬浉閭诲厓绱狅紝濡傛灉閫嗗簭锛屽垯浜ゆ崲銆傛瘡娆″啋娉★紝鏈澶х殑鍏冪礌閮戒細琚尓鍒板悗闈紝鍏跺疄鍜岄夋嫨鎺掑簭鏄浉閫嗙殑銆
….
鍙戣〃鍥炲