{"id":2794,"date":"2016-08-06T23:36:23","date_gmt":"2016-08-06T15:36:23","guid":{"rendered":"http:\/\/ixyzero.com\/blog\/?p=2794"},"modified":"2016-08-06T23:36:23","modified_gmt":"2016-08-06T15:36:23","slug":"collect%e5%b8%b8%e8%a7%81%e7%ae%97%e6%b3%95%e7%9a%84%e6%97%b6%e7%a9%ba%e5%a4%8d%e6%9d%82%e5%ba%a6%e5%a4%87%e5%bf%98%e6%b8%85%e5%8d%95","status":"publish","type":"post","link":"https:\/\/ixyzero.com\/blog\/archives\/2794.html","title":{"rendered":"[collect]\u5e38\u89c1\u7b97\u6cd5\u7684\u65f6\u7a7a\u590d\u6742\u5ea6\u5907\u5fd8\u6e05\u5355"},"content":{"rendered":"<p>=Start=<\/p>\n<h5>\u7f18\u7531\uff1a<\/h5>\n<p>\u4e86\u89e3\u5e38\u89c1\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u7a7a\u95f4\u590d\u6742\u5ea6\u5bf9\u4e8e\u4e00\u540d\u7a0b\u5e8f\u5458\u6765\u8bf4\u662f\u5927\u6709\u88e8\u76ca\u7684\u2014\u2014\u4e0d\u8bba\u662f\u51c6\u5907\u8003\u8bd5\u3001\u9762\u8bd5\uff0c\u8fd8\u662f\u65b9\u4fbf\u81ea\u5df1\u5b66\u4e60\u3001\u8bc6\u8bb0\u3002<\/p>\n<p>\u4ee5\u5f80\u6211\u5728\u53c2\u52a0\u9762\u8bd5\u524d\uff0c\u7ecf\u5e38\u9700\u8981\u82b1\u8d39\u5f88\u591a\u65f6\u95f4\u4ece\u4e92\u8054\u7f51\u4e0a\u67e5\u627e\u5404\u79cd\u641c\u7d22\u548c\u6392\u5e8f\u7b97\u6cd5\u7684\u4f18\u52a3\uff0c\u4ee5\u4fbf\u6211\u5728\u9762\u8bd5\u65f6\u4e0d\u4f1a\u88ab\u95ee\u4f4f\u3002\u4e5f\u6709\u9488\u5bf9\u6027\u505a\u4e86\u4e00\u4e9b\u7b14\u8bb0\uff0c\u4f46\u65f6\u95f4\u4e00\u957f\uff0c\u4e4b\u524d\u505a\u7684\u4e00\u4e9b\u8bb0\u5f55\u5c31\u90fd\u4e0d\u77e5\u9053\u653e\u5728\u54ea\u53bb\u4e86\uff0c\u4f46\u73b0\u5728\u6211\u4eec\u53ef\u4ee5\u901a\u8fc7 Eric \u521b\u5efa\u7684 BigOCheatSheet \u5feb\u901f\u7684\u4e86\u89e3\u5e38\u89c1\u7b97\u6cd5\u7684\u65f6\u7a7a\u590d\u6742\u5ea6\uff0c\u7701\u65f6\u7701\u529b\uff0c\u5b9e\u4e43\u5c45\u5bb6\u65c5\u884c\u5fc5\u5907\u795e\u5668\u3002<\/p>\n<h5>\u6b63\u6587\uff1a<\/h5>\n<h6 id=\"data-structures\">\u6570\u636e\u7ed3\u6784\u64cd\u4f5c<\/h6>\n<table class=\"table table-striped\" border=\"1\" cellpadding=\"4\">\n<thead>\n<tr>\n<th>\u6570\u636e\u7ed3\u6784<\/th>\n<th colspan=\"8\">\u65f6\u95f4\u590d\u6742\u5ea6<\/th>\n<th>\u7a7a\u95f4\u590d\u6742\u5ea6<\/th>\n<\/tr>\n<tr>\n<th><\/th>\n<th colspan=\"4\">\u5e73\u5747<\/th>\n<th colspan=\"4\">\u6700\u5dee<\/th>\n<th>\u6700\u5dee<\/th>\n<\/tr>\n<tr>\n<th><\/th>\n<th>\u8bbf\u95ee<\/th>\n<th>\u641c\u7d22<\/th>\n<th>\u63d2\u5165<\/th>\n<th>\u5220\u9664<\/th>\n<th>\u8bbf\u95ee<\/th>\n<th>\u641c\u7d22<\/th>\n<th>\u63d2\u5165<\/th>\n<th>\u5220\u9664<\/th>\n<th><\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Array_data_structure\" target=\"_blank\" rel=\"external nofollow\">Array<\/a><\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Stack_(abstract_data_type)\" target=\"_blank\" rel=\"external nofollow\">Stack<\/a><\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Singly_linked_list#Singly_linked_lists\" target=\"_blank\" rel=\"external nofollow\">Singly-Linked List<\/a><\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Doubly_linked_list\" target=\"_blank\" rel=\"external nofollow\">Doubly-Linked List<\/a><\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Skip_list\" target=\"_blank\" rel=\"external nofollow\">Skip List<\/a><\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n log(n))<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Hash_table\" target=\"_blank\" rel=\"external nofollow\">Hash Table<\/a><\/td>\n<td>&#8211;<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>O(1)<\/td>\n<td>&#8211;<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Binary_search_tree\" target=\"_blank\" rel=\"external nofollow\">Binary Search Tree<\/a><\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"https:\/\/en.wikipedia.org\/wiki\/Cartesian_tree\" target=\"_blank\" rel=\"external nofollow\">Cartesian Tree<\/a><\/td>\n<td>&#8211;<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>&#8211;<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/B_tree\" target=\"_blank\" rel=\"external nofollow\">B-Tree<\/a><\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Red-black_tree\" target=\"_blank\" rel=\"external nofollow\">Red-Black Tree<\/a><\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"https:\/\/en.wikipedia.org\/wiki\/Splay_tree\" target=\"_blank\" rel=\"external nofollow\">Splay Tree<\/a><\/td>\n<td>&#8211;<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>&#8211;<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/AVL_tree\" target=\"_blank\" rel=\"external nofollow\">AVL Tree<\/a><\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(log(n))<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h6 id=\"sorting\">\u6570\u7ec4\u6392\u5e8f\u7b97\u6cd5<\/h6>\n<table class=\"table table-striped\" border=\"1\" cellpadding=\"4\">\n<thead>\n<tr>\n<th>\u7b97\u6cd5<\/th>\n<th colspan=\"3\">\u65f6\u95f4\u590d\u6742\u5ea6<\/th>\n<th>\u7a7a\u95f4\u590d\u6742\u5ea6<\/th>\n<\/tr>\n<tr>\n<th><\/th>\n<th>\u6700\u4f73<\/th>\n<th>\u5e73\u5747<\/th>\n<th>\u6700\u5dee<\/th>\n<th>\u6700\u5dee<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Quicksort\" target=\"_blank\" rel=\"external nofollow\">Quicksort<\/a><\/td>\n<td>O(n log(n))<\/td>\n<td>O(n log(n))<\/td>\n<td>O(n^2)<\/td>\n<td>O(log(n))<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Merge_sort\" target=\"_blank\" rel=\"external nofollow\">Mergesort<\/a><\/td>\n<td>O(n log(n))<\/td>\n<td>O(n log(n))<\/td>\n<td>O(n log(n))<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Timsort\" target=\"_blank\" rel=\"external nofollow\">Timsort<\/a><\/td>\n<td>O(n)<\/td>\n<td>O(n log(n))<\/td>\n<td>O(n log(n))<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Heapsort\" target=\"_blank\" rel=\"external nofollow\">Heapsort<\/a><\/td>\n<td>O(n log(n))<\/td>\n<td>O(n log(n))<\/td>\n<td>O(n log(n))<\/td>\n<td>O(1)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Bubble_sort\" target=\"_blank\" rel=\"external nofollow\">Bubble Sort<\/a><\/td>\n<td>O(n)<\/td>\n<td>O(n^2)<\/td>\n<td>O(n^2)<\/td>\n<td>O(1)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Insertion_sort\" target=\"_blank\" rel=\"external nofollow\">Insertion Sort<\/a><\/td>\n<td>O(n)<\/td>\n<td>O(n^2)<\/td>\n<td>O(n^2)<\/td>\n<td>O(1)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Selection_sort\" target=\"_blank\" rel=\"external nofollow\">Selection Sort<\/a><\/td>\n<td>O(n^2)<\/td>\n<td>O(n^2)<\/td>\n<td>O(n^2)<\/td>\n<td>O(1)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" href=\"http:\/\/en.wikipedia.org\/wiki\/Shellsort\" target=\"_blank\" rel=\"external nofollow\">Shell Sort<\/a><\/td>\n<td>O(n)<\/td>\n<td>O((nlog(n))^2)<\/td>\n<td>O((nlog(n))^2)<\/td>\n<td>O(1)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" title=\"Only for integers. k is a number of buckets\" href=\"http:\/\/en.wikipedia.org\/wiki\/Bucket_sort\" target=\"_blank\" rel=\"external nofollow\">Bucket Sort<\/a><\/td>\n<td>O(n+k)<\/td>\n<td>O(n+k)<\/td>\n<td>O(n^2)<\/td>\n<td>O(n)<\/td>\n<\/tr>\n<tr>\n<td><a class=\"ext\" title=\"Constant number of digits 'k'\" href=\"http:\/\/en.wikipedia.org\/wiki\/Radix_sort\" target=\"_blank\" rel=\"external nofollow\">Radix Sort<\/a><\/td>\n<td>O(nk)<\/td>\n<td>O(nk)<\/td>\n<td>O(nk)<\/td>\n<td>O(n+k)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h6>\u5927O\u590d\u6742\u5ea6\u56fe\u8868<\/h6>\n<p><a href=\"http:\/\/ixyzero.com\/blog\/wp-content\/uploads\/2016\/08\/bigOcomplexity.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-2795\" src=\"http:\/\/ixyzero.com\/blog\/wp-content\/uploads\/2016\/08\/bigOcomplexity.png\" alt=\"bigOcomplexity\" width=\"783\" height=\"454\" \/><\/a><\/p>\n<h5>\u53c2\u8003\u94fe\u63a5\uff1a<\/h5>\n<ul>\n<li>\u539f\u6587\u94fe\u63a5\uff1a<a href=\"https:\/\/linux.cn\/article-7480-1.html?pr\" target=\"_blank\">\u6bcf\u4e2a\u7a0b\u5e8f\u5458\u90fd\u5e94\u8be5\u6536\u85cf\u7684\u7b97\u6cd5\u590d\u6742\u5ea6\u901f\u67e5\u8868<\/a><\/li>\n<li>\u82f1\u6587\u94fe\u63a5\uff1a<a href=\"http:\/\/bigocheatsheet.com\/\" target=\"_blank\">http:\/\/bigocheatsheet.com\/<\/a><\/li>\n<li>GitHub\u5730\u5740\uff1a<a href=\"https:\/\/github.com\/ericdrowell\/BigOCheatSheet\" target=\"_blank\">BigOCheatSheet<\/a><\/li>\n<\/ul>\n<p>=END=<\/p>\n","protected":false},"excerpt":{"rendered":"<p>=Start= \u7f18\u7531\uff1a \u4e86\u89e3\u5e38\u89c1\u7b97\u6cd5\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u548c\u7a7a\u95f4\u590d\u6742\u5ea6\u5bf9\u4e8e\u4e00\u540d\u7a0b\u5e8f\u5458\u6765\u8bf4\u662f\u5927\u6709\u88e8\u76ca\u7684\u2014\u2014\u4e0d\u8bba\u662f\u51c6\u5907\u8003\u8bd5\u3001 [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23,7,12],"tags":[640,512,292],"class_list":["post-2794","post","type-post","status-publish","format-standard","hentry","category-knowledgebase-2","category-programing","category-tools","tag-algorithms","tag-complexity","tag-sort"],"views":6885,"_links":{"self":[{"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/posts\/2794","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/comments?post=2794"}],"version-history":[{"count":0,"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/posts\/2794\/revisions"}],"wp:attachment":[{"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/media?parent=2794"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/categories?post=2794"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/ixyzero.com\/blog\/wp-json\/wp\/v2\/tags?post=2794"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}