C语言，时间复杂度与空间复杂度，算法时间公式T(n)=O(f(n))，与空间公式S(n)=O（f（n）） 时间复杂度 T(n)=O(f(n)),的 O什么意思
\u7b97\u6cd5\u8bbe\u8ba1\u4e0e\u5206\u6790 \u5df2\u77e5\u67d0\u4e2a\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6T(n)=O(f(n))\uff0cf(n)\u662f\u4ec0\u4e48\u51fd\u6570\uff1fT(n)\u548cf(n)\u662f\u4ec0\u4e48\u5173\u7cfb\uff1f\u65f6\u95f4\u590d\u6742\u5ea6
\u7b97\u6cd5\u5206\u6790
\u540c\u4e00\u95ee\u9898\u53ef\u7528\u4e0d\u540c\u7b97\u6cd5\u89e3\u51b3\uff0c\u800c\u4e00\u4e2a\u7b97\u6cd5\u7684\u8d28\u91cf\u4f18\u52a3\u5c06\u5f71\u54cd\u5230\u7b97\u6cd5\u4e43\u81f3\u7a0b\u5e8f\u7684\u6548\u7387\u3002\u7b97\u6cd5\u5206\u6790\u7684\u76ee\u7684\u5728\u4e8e\u9009\u62e9\u5408\u9002\u7b97\u6cd5\u548c\u6539\u8fdb\u7b97\u6cd5\u3002\u4e00\u4e2a\u7b97\u6cd5\u7684\u8bc4\u4ef7\u4e3b\u8981\u4ece\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u7a7a\u95f4\u590d\u6742\u5ea6\u6765\u8003\u8651\u3002
1\u3001\u65f6\u95f4\u590d\u6742\u5ea6
\uff081\uff09\u65f6\u95f4\u9891\u5ea6
\u4e00\u4e2a\u7b97\u6cd5\u6267\u884c\u6240\u8017\u8d39\u7684\u65f6\u95f4\uff0c\u4ece\u7406\u8bba\u4e0a\u662f\u4e0d\u80fd\u7b97\u51fa\u6765\u7684\uff0c\u5fc5\u987b\u4e0a\u673a\u8fd0\u884c\u6d4b\u8bd5\u624d\u80fd\u77e5\u9053\u3002\u4f46\u6211\u4eec\u4e0d\u53ef\u80fd\u4e5f\u6ca1\u6709\u5fc5\u8981\u5bf9\u6bcf\u4e2a\u7b97\u6cd5\u90fd\u4e0a\u673a\u6d4b\u8bd5\uff0c\u53ea\u9700\u77e5\u9053\u54ea\u4e2a\u7b97\u6cd5\u82b1\u8d39\u7684\u65f6\u95f4\u591a\uff0c\u54ea\u4e2a\u7b97\u6cd5\u82b1\u8d39\u7684\u65f6\u95f4\u5c11\u5c31\u53ef\u4ee5\u4e86\u3002\u5e76\u4e14\u4e00\u4e2a\u7b97\u6cd5\u82b1\u8d39\u7684\u65f6\u95f4\u4e0e\u7b97\u6cd5\u4e2d\u8bed\u53e5\u7684\u6267\u884c\u6b21\u6570\u6210\u6b63\u6bd4\u4f8b\uff0c\u54ea\u4e2a\u7b97\u6cd5\u4e2d\u8bed\u53e5\u6267\u884c\u6b21\u6570\u591a\uff0c\u5b83\u82b1\u8d39\u65f6\u95f4\u5c31\u591a\u3002\u4e00\u4e2a\u7b97\u6cd5\u4e2d\u7684\u8bed\u53e5\u6267\u884c\u6b21\u6570\u79f0\u4e3a\u8bed\u53e5\u9891\u5ea6\u6216\u65f6\u95f4\u9891\u5ea6\u3002\u8bb0\u4e3aT(n)\u3002
\uff082\uff09\u65f6\u95f4\u590d\u6742\u5ea6
\u5728\u521a\u624d\u63d0\u5230\u7684\u65f6\u95f4\u9891\u5ea6\u4e2d\uff0cn\u79f0\u4e3a\u95ee\u9898\u7684\u89c4\u6a21\uff0c\u5f53n\u4e0d\u65ad\u53d8\u5316\u65f6\uff0c\u65f6\u95f4\u9891\u5ea6T(n)\u4e5f\u4f1a\u4e0d\u65ad\u53d8\u5316\u3002\u4f46\u6709\u65f6\u6211\u4eec\u60f3\u77e5\u9053\u5b83\u53d8\u5316\u65f6\u5448\u73b0\u4ec0\u4e48\u89c4\u5f8b\u3002\u4e3a\u6b64\uff0c\u6211\u4eec\u5f15\u5165\u65f6\u95f4\u590d\u6742\u5ea6\u6982\u5ff5\u3002
\u4e00\u822c\u60c5\u51b5\u4e0b\uff0c\u7b97\u6cd5\u4e2d\u57fa\u672c\u64cd\u4f5c\u91cd\u590d\u6267\u884c\u7684\u6b21\u6570\u662f\u95ee\u9898\u89c4\u6a21n\u7684\u67d0\u4e2a\u51fd\u6570\uff0c\u7528T(n)\u8868\u793a\uff0c\u82e5\u6709\u67d0\u4e2a\u8f85\u52a9\u51fd\u6570f(n),\u4f7f\u5f97\u5f53n\u8d8b\u8fd1\u4e8e\u65e0\u7a77\u5927\u65f6\uff0cT\uff08n)/f(n)\u7684\u6781\u9650\u503c\u4e3a\u4e0d\u7b49\u4e8e\u96f6\u7684\u5e38\u6570\uff0c\u5219\u79f0f(n)\u662fT(n)\u7684\u540c\u6570\u91cf\u7ea7\u51fd\u6570\u3002\u8bb0\u4f5cT(n)=O(f(n)),\u79f0O(f(n)) \u4e3a\u7b97\u6cd5\u7684\u6e10\u8fdb\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u7b80\u79f0\u65f6\u95f4\u590d\u6742\u5ea6\u3002
\u5728\u5404\u79cd\u4e0d\u540c\u7b97\u6cd5\u4e2d\uff0c\u82e5\u7b97\u6cd5\u4e2d\u8bed\u53e5\u6267\u884c\u6b21\u6570\u4e3a\u4e00\u4e2a\u5e38\u6570\uff0c\u5219\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(1),\u53e6\u5916\uff0c\u5728\u65f6\u95f4\u9891\u5ea6\u4e0d\u76f8\u540c\u65f6\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u6709\u53ef\u80fd\u76f8\u540c\uff0c\u5982T(n)=n2+3n+4\u4e0eT(n)=4n2+2n+1\u5b83\u4eec\u7684\u9891\u5ea6\u4e0d\u540c\uff0c\u4f46\u65f6\u95f4\u590d\u6742\u5ea6\u76f8\u540c\uff0c\u90fd\u4e3aO(n2)\u3002
\u6309\u6570\u91cf\u7ea7\u9012\u589e\u6392\u5217\uff0c\u5e38\u89c1\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u6709\uff1a
\u5e38\u6570\u9636O(1),\u5bf9\u6570\u9636O(log2n),\u7ebf\u6027\u9636O(n),
\u7ebf\u6027\u5bf9\u6570\u9636O(nlog2n),\u5e73\u65b9\u9636O(n2)\uff0c\u7acb\u65b9\u9636O(n3),...\uff0c
k\u6b21\u65b9\u9636O(nk),\u6307\u6570\u9636O(2n)\u3002\u968f\u7740\u95ee\u9898\u89c4\u6a21n\u7684\u4e0d\u65ad\u589e\u5927\uff0c\u4e0a\u8ff0\u65f6\u95f4\u590d\u6742\u5ea6\u4e0d\u65ad\u589e\u5927\uff0c\u7b97\u6cd5\u7684\u6267\u884c\u6548\u7387\u8d8a\u4f4e\u3002
O(n)\u8fd9\u4e2a\u5927O\u8868\u793a\u7684\u662f\u6700\u574f\u60c5\u51b5\u4e0b\u7684\u65f6\u95f4\u590d\u6742\u5ea6\uff0c\u5c31\u6bd4\u5982\u4f60\u4e3e\u7684\u4f8b\u5b50\uff0c\u4e00\u5171n^3\u6b21\u4e58\u6cd5\u548cn^3\u6b21\u52a0\u6cd5\uff0c\u90a3\u4e48\u52a0\u8d77\u6765\u5c31\u662f2\u00d7n^3\u3002\u7136\u540e\u5982\u679c\u6709\u4e00\u4e2a\u8868\u8fbe\u5f0ff(n)\uff0c\u4f7f\u5f97n\u8d8b\u4e8e\u65e0\u7a77\u5927\u7684\u65f6\u5019\uff0clim(2\u00d7n^3)/f(n)=\u5e38\u6570c\uff0c\u90a3\u4e48\u5c31\u53ef\u4ee5\u7528\u5927O\u8868\u793a\u3002\u8868\u793a\u4e3aO(f(n))\uff0c\u800c\u4e14\u89c4\u5b9af(n)\u7684\u8868\u8fbe\u5f0f\u662f\u4e0d\u5e26\u5e38\u6570\u7684\u7cfb\u6570\u7684\uff0c\u90a3\u4e48\u5728\u8fd9\u91ccf(n)=n^3\u3002\u4e00\u822c\u7528\u5927O\u8868\u793a\u7b97\u6cd5\u590d\u6742\u5ea6\u53ea\u9700\u8981\u53d6\u6b21\u6570\u6700\u9ad8\u7684\u9879\uff0c\u800c\u4e14\u53bb\u6389\u7cfb\u6570\u5c31OK\u4e86\uff0c\u4e0d\u7528\u6bcf\u6b21\u90fd\u8fd9\u4e48\u7b97\u7684\u3002\u4e09\u91cd\u5faa\u73af\u800c\u4e14\u6bcf\u91cd\u5faa\u73af\u90fd\u6267\u884cn\u6b21\u7684\u8bdd\u76f4\u63a5O(n^3)\u5c31\u597d\u4e86\u3002
算法的时间复杂度：为了便于比较同一问题的不同算法，通常从算法中抽取一种或者多种有代表性的基本操作，再以这些基本操作重复执行的次数与问题规模的关系T(n) 作为算法的时间性量度。
如果T(n) 和 f(n) 是n 的函数，当n →∞ 时，有T(n) / f(n) → c (常数c ≠ 0)，记作：T(n) = O(f(n))，称O(f(n)) 为算法的渐近时间复杂度，简称时间复杂度。
算法的空间复杂度：
一个算法实现所占存储空间大致包含三方面：
1. 指令、常数、变量所占用的存储空间；
2. 输入数据所占用的存储空间；
3. 算法执行时所需的辅助空间；
前两者是必须的，通常将算法执行时所需的辅助空间作为分析算法空间复杂度的依据：S(n) = O(f(n))，其中f(n)的规则与时间复杂度一致。
绛旓細闅忕潃杈撳叆鐨勫鍔狅紝涓嶅悓绠楁硶鐨勫鏉傚害澧為暱閫熷害涓轰簡闄嶄綆绠楁硶澶嶆潅搴︼紝搴斿綋鍚屾椂鑰冭檻鍒拌緭鍏ラ噺锛岃璁¤緝濂界殑绠楁硶銆傚悓涓闂鍙敤涓嶅悓绠楁硶瑙ｅ喅锛岃屼竴涓畻娉曠殑璐ㄩ噺浼樺姡灏嗗奖鍝嶅埌绠楁硶涔冭嚦绋嬪簭鐨勬晥鐜囥傜畻娉曞垎鏋愮殑鐩殑鍦ㄤ簬閫夋嫨鍚堥傜畻娉曞拰鏀硅繘绠楁硶銆備竴涓畻娉曠殑璇勪环涓昏浠鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴鏉ヨ冭檻銆
绛旓細绠楁硶澶嶆潅搴︿富瑕佸寘鎷鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴瑙ｉ噴濡備笅锛氱畻娉曠殑鏃堕棿澶嶆潅搴︽槸鎸囧绠楁硶鎵ц鏃舵墍鑺辨椂闂寸殑搴﹂噺銆備竴鑸负闂瑙勬ā鐨勫嚱鏁般傝绠楁満绉戝涓紝绠楁硶鐨勬椂闂村鏉傚害鏄竴涓嚱鏁帮紝瀹冨畾閲忔弿杩颁簡璇ョ畻娉曠殑杩愯鏃堕棿銆傜畻娉曠殑澶嶆潅搴︿富瑕佸寘鎷椂闂村鏉傚害鍜岀┖闂村鏉傚害銆傜畻娉曠殑鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴﹀悎绉颁负绠楁硶鐨勫鏉傚害銆
绛旓細浠涔堟槸绠楁硶鐨鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴 绠楁硶鏄绠楁満绉戝涓殑涓涓噸瑕佹蹇点傚湪璁＄畻鏈轰腑锛岀畻娉曟槸涓绯诲垪鏈夋晥鐨勬搷浣滄楠わ紝鐢ㄤ簬瑙ｅ喅鐗瑰畾闂鐨勬柟娉曘傜畻娉曠殑鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴︽槸琛￠噺绠楁硶鏁堢巼鐨勪袱涓噸瑕佹寚鏍囥傛椂闂村鏉傚害鏄寚绠楁硶瀹屾垚鎵闇鐨勬椂闂达紝閫氬父浠ユ搷浣滄鏁颁负鍗曚綅锛岃岀┖闂村鏉傚害鏄寚绠楁硶瀹屾垚鎵闇鐨勫唴瀛樼┖闂...
绛旓細绠楁硶鐨鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴鏄弿杩扮畻娉曟ц兘鐨勪袱涓噸瑕佹寚鏍囥傚畠浠箣闂存病鏈夌洿鎺ョ殑鏁板鍏崇郴锛岃屾槸鐩镐簰鐙珛鐨勩傛椂闂村鏉傚害锛圱imeComplexity锛夋槸琛￠噺绠楁硶鎵ц鏃堕棿闅忚緭鍏ヨ妯″闀胯屽彉鍖栫殑搴﹂噺銆傚畠閫氬父鐢ㄥぇO绗﹀彿琛ㄧず锛屾瘮濡侽锛坣锛夈丱锛坣logn锛夌瓑銆傛椂闂村鏉傚害鎻忚堪鐨勬槸绠楁硶鎵闇鎵ц鐨勫熀鏈搷浣滄暟鐩紝鍗崇畻娉曠殑杩愯鏃堕棿...
绛旓細鏃堕棿澶嶆潅搴︿笌绌洪棿澶嶆潅搴娌℃湁蹇呯劧鑱旂郴銆備絾鏄篃鏈変互绌洪棿鎹㈡椂闂存垨鏃堕棿鎹㈢┖闂寸殑锛屾鏃讹紝瀹冧滑灏变細鏈夊奖鍝嶃傚儚鏁ｅ垪娉曪紝鐢ㄦ洿澶氱殑绌洪棿锛屼絾鏃堕棿浼氬皬浜嶰(n)銆鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴︼紝鍏跺疄灏辨槸鎵鑰楁椂闂翠笌绌洪棿鍏充簬杈撳叆鏁版嵁瑙勬ā鐨勫嚱鏁帮紝涓鑸緭鍏ユ暟鎹妯¤秺澶э紝鎵鑰楁椂闂村拰绌洪棿灏辫秺澶氾紝濡傛灉鎵鑰楁椂闂翠笌鏁版嵁瑙勬ā鎴愭姣斻
绛旓細鏃堕棿澶嶆潅搴锛屽氨鏄绠绋嬪簭杩愯鐨鏃堕棿锛岀┖闂村鏉傚害锛 灏辨槸鎵鍗犵殑鍐呭瓨绌洪棿銆傚悓涓闂鍙敤涓嶅悓绠楁硶瑙ｅ喅锛岃屼竴涓畻娉曠殑璐ㄩ噺浼樺姡灏嗗奖鍝嶅埌绠楁硶涔冭嚦绋嬪簭鐨勬晥鐜囥傜畻娉曞垎鏋愮殑鐩殑鍦ㄤ簬閫夋嫨鍚堥傜畻娉曞拰鏀硅繘绠楁硶銆傝绠楁満绉戝涓紝绠楁硶鐨勬椂闂村鏉傚害鏄竴涓嚱鏁帮紝瀹冨畾閲忔弿杩颁簡璇ョ畻娉曠殑杩愯鏃堕棿銆傝繖鏄竴涓叧浜庝唬琛ㄧ畻娉曡緭鍏ュ肩殑...
绛旓細瑕佸疄鐜版寜瀛楃璇诲叆C婧绋嬪簭骞剁粺璁￠『搴忔墽琛屽惊鐜墽琛岀殑鎵ц娆℃暟锛屾垜浠彲浠ヤ娇鐢ㄤ互涓嬫楠わ細1. 鎵撳紑C婧愮▼搴忔枃浠躲2. 閫愬瓧绗﹁鍙栨枃浠跺唴瀹广3. 浣跨敤涓涓鏁板櫒鏉ョ粺璁″惊鐜墽琛岀殑娆℃暟銆4. 鍒嗘瀽浠ｇ爜鐨鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴銆備互涓嬫槸涓涓畝鍗曠殑C++瀹炵幇锛歚``cpp include include include int main() { std::...
绛旓細鍦ㄨ绠楁満绉戝涓紝褰撴垜浠瘎浠蜂竴涓畻娉曟椂锛岄氬父浼氳冭檻涓や釜涓昏鐨勬爣鍑嗭細绌洪棿澶嶆潅搴﹀拰鏃堕棿澶嶆潅搴銆傝繖涓や釜鏍囧噯鍦ㄥ緢澶х▼搴︿笂鍐冲畾浜嗙畻娉曠殑鏁堢巼鍜屽疄鐢ㄦс1銆佺┖闂村鏉傚害锛氱┖闂村鏉傚害琛￠噺鐨勬槸绠楁硶鍦ㄨ繍琛岃繃绋嬩腑鎵闇浣跨敤鐨勫瓨鍌ㄧ┖闂淬傝繖鍙兘鍖呮嫭鍙橀噺銆佹暟鎹粨鏋勶紙濡傛暟缁勬垨鍫嗘爤锛夈佷复鏃跺伐浣滅┖闂寸瓑銆傜┖闂村鏉傚害閫氬父鐢ㄨ緭鍏...
绛旓細 绠楁硶鏃堕棿澶嶆潅搴鍒嗘瀽鏄竴涓緢閲嶈鐨勯棶棰,浠讳綍涓涓绋嬪簭鍛橀兘搴旇鐔熺粌鎺屾彙鍏舵蹇靛拰鍩烘湰鏂规硶,鑰屼笖瑕佸杽浜庝粠鏁板灞傞潰涓婃帰瀵诲叾鏈川,鎵嶈兘鍑嗙‘鐞嗚В鍏跺唴娑点 2銆佺畻娉曠殑绌洪棿澶嶆潅搴 绫讳技浜庢椂闂村鏉傚害鐨勮璁,涓涓畻娉曠殑绌洪棿澶嶆潅搴(Space Complexity)S(n)瀹氫箟涓鸿绠楁硶鎵鑰楄垂鐨勫瓨鍌ㄧ┖闂,瀹冧篃鏄棶棰樿妯鐨勫嚱鏁般傛笎杩戠┖闂...
绛旓細闂鍏細C璇█涓┖闂村鏉傚害O(1)鏄粈涔堟剰鎬濆晩锛 绌洪棿澶嶆潅搴︽槸瀵逛竴涓畻娉曞湪杩愯杩囩▼涓复鏃跺崰鐢ㄥ瓨鍌ㄧ┖闂村ぇ灏忕殑閲忓害銆傚褰撲竴涓畻娉曠殑绌洪棿澶嶆潅搴︿负涓涓父閲忥紝鍗充笉闅忚澶勭悊鏁版嵁閲弉鐨勫ぇ灏忚屾敼鍙樻椂锛屽彲琛ㄧず涓篛(1)闂涓冿細c锛嬶紜鏃堕棿澶嶆潅搴﹀拰绌洪棿澶嶆潅搴鏄粈涔堜笢瑗 绠鍗曟潵璁叉椂闂村鏉傚害灏辨槸璁＄畻鏃堕棿锛绌洪棿...
