{"id":552,"date":"2007-03-15T11:22:00","date_gmt":"2007-03-15T03:22:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=552"},"modified":"2023-11-04T11:23:42","modified_gmt":"2023-11-04T03:23:42","slug":"data-structures-concept","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/552","title":{"rendered":"Data Structures Concept"},"content":{"rendered":"\n

\u8cc7\u8a0a\u79d1\u5b78<\/strong>\u662f\u63a2\u8a0e\u6f14\u7b97\u6cd5\u5247\u8207\u8cc7\u6599\u7d50\u69cb\u7684\u79d1\u5b78,\u4f7f\u7528\u6700\u9069\u7576\u7684\u8cc7\u6599\u7d50\u69cb<\/strong>,\u624d\u80fd\u5920\u8a2d\u8a08\u51fa\u6700\u6709\u6548\u7387\u7684\u6f14\u7b97\u6cd5\u5247<\/strong>
\u8cc7\u6599\u7d50\u69cb:\u63a2\u8a0e\u4e00\u7fa4\u76f8\u95dc\u8cc7\u6599\u7684\u8cc7\u6599\u8868\u793a\u65b9\u6cd5\u8207\u8cc7\u6599\u904b\u4f5c\u65b9\u6cd5<\/p>\n\n\n\n

ADT(abstract data type,\u62bd\u8c61\u5316\u8cc7\u6599\u578b\u614b)\uff1a\u4e00\u7a2e\u8cc7\u6599\u578b\u614b,\u5fc5\u9700\u6eff\u8db3\u5305\u88dd\u8207\u8cc7\u8a0a\u96b1\u85cf\u5169\u500b\u689d\u4ef6
\u5305\u88dd:\u8cc7\u6599\u8868\u793a\u65b9\u6cd5\u548c\u904b\u7b97\u65b9\u6cd5,\u9700\u5728\u4e00\u7279\u6b8a\u7684\u7a0b\u5f0f\u55ae\u5143\u5167\u5ba3\u544a\u8207\u63cf\u8ff0,\u76ee\u5730:\u8b93\u4e4b\u5f8c\u7684\u4fee\u6539\u80fd\u5728\u6b64\u7279\u6b8a\u7684\u7a0b\u5f0f\u55ae\u5143\u4e2d\u9032\u884c
\u8cc7\u8a0a\u96b1\u85cf:\u5305\u88dd\u9700\u96b1\u85cf,\u4e0d\u53ef\u8b93\u4f7f\u7528\u62bd\u8c61\u5316\u8cc7\u6599\u578b\u614b\u7684\u7a0b\u5f0f\u5f97\u77e5,\u76ee\u5730:\u8b93\u7a0b\u5f0f\u4e0d\u9700\u96a8\u8457\u62bd\u8c61\u5316\u578b\u614b\u5167\u90e8\u8868\u793a\u65b9\u5f0f\u6539\u8b8a\u800c\u4fee\u6539<\/p>\n\n\n\n

\u8cc7\u6599\u7684\u908f\u8f2f\u95dc\u4fc2\u5206\u70ba\uff1a
\u7dda\u6027\u95dc\u6027(\u5b58\u5728\u5148\u5f8c\u9806\u5e8f)
\u968e\u5c64\u95dc\u4fc2(\u8cc7\u6599\u6709\u4e0a\u4e0b\u968e\u5c64\uff0c\u5b58\u5728\u5305\u542b\u95dc\u4fc2)
\u76f8\u9130\u95dc\u4fc2(\u8cc7\u6599\u4e92\u9023)<\/p>\n\n\n\n

\u8cc7\u6599\u8868\u793a\u6cd5\u5206\u70ba:
\u5faa\u5e8f\u8868\u793a\u6cd5(\u9663\u5217):\u8cc7\u6599\u908f\u8f2f\u9806\u5e8f\u8207\u5132\u5b58\u5728\u8a18\u61b6\u9ad4\u7684\u5be6\u969b\u9806\u5e8f\u76f8\u540c
\u93c8\u7d50\u8868\u793a\u6cd5(\u93c8\u7d50\u4e32\u5217):\u8cc7\u6599\u908f\u8f2f\u9806\u5e8f\u8207\u8207\u5b58\u5728\u8a18\u61b6\u9ad4\u7684\u5be6\u969b\u9806\u5e8f\u4e0d\u540c<\/p>\n\n\n\n

\u5e38\u898b\u7684\u8cc7\u6599\u578b\u614b\u6709:
\u9663\u5217\u578b\u614b
\u7d50\u69cb\u578b\u614b
\u6307\u6a19\u578b\u614b<\/p>\n\n\n\n

……………………………………………………<\/p>\n\n\n\n


\u6f14\u7b97\u6cd5\u9700\u5177\u5099
output(\u8f38\u51fa\u6027):\u81f3\u5c11\u8981\u7522\u751f\u4e00\u500b\u7d50\u679c
definitieness(\u660e\u78ba\u6027):\u5404\u6b65\u9a5f\u63cf\u8ff0\u9808\u5341\u5206\u660e\u78ba(\u63cf\u8ff0\u5de5\u5177\u6709\u81ea\u7136\u8a9e\u8a00,\u7a0b\u5f0f\u8a9e\u8a00,\u6d41\u7a0b\u5716,\u865b\u64ec\u78bc)
effectiveness(\u6709\u9650\u6027):\u9700\u5728\u6709\u9650\u6b65\u9a5f\u5167\u7d50\u675f
finiteness(\u6709\u6548\u6027):\u5404\u6b65\u9a5f\u53ef\u88ab\u57f7\u884c,\u5177\u53ef\u884c\u6027,\u4e14\u4e0d\u53ef\u6216\u7f3a<\/p>\n\n\n\n

\u6f14\u7b97\u6cd5\u5247\u7684\u57fa\u672c\u6b65\u9a5f:
sequence(\u5faa\u5e8f\u6b65\u9a5f)
selection(\u9078\u64c7\u6b65\u9a5f)
iteration(\u91cd\u8986\u6b65\u9a5f)<\/p>\n\n\n\n

………………..<\/p>\n\n\n\n

\u8907\u96dc\u5ea6\u7b26\u865f:<\/strong>
big omega:<\/strong>
lower bound\u8907\u96dc\u5ea6\u4e0b\u9650(\u6700\u4f73\u60c5\u6cc1),\u5206\u6790\u6f14\u7b97\u6cd5\u662f\u5426\u5df1\u6700\u4f73\u5316
\u82e5f(N)=big omega(g(N))\u6210\u7acb\u6642,\u5247\u5b58\u57282\u500b\u5e38\u6578C,N0,\u4f7f\u5f97|f(N)|>=C|g(N)|,\u7576N>=N0
omega<\/strong>
big omega\u53bb\u6389theta\u90e8\u4efd
big O:<\/strong>
upper bound\u8907\u96dc\u5ea6\u4e0a\u9650(\u6700\u5dee\u60c5\u6cc1),\u5ffd\u7565\u5e38\u6578\u53ea\u53d6\u6700\u9ad8\u6b21\u65b9\u9805\u5373\u53ef\u5f97
\u82e5f(N)=big O(g(N))\u6210\u7acb\u6642,\u5247\u5b58\u57282\u500b\u5b58\u6578C,N0,\u4f7f\u5f97|f(N)|<=C|g(N)|,\u7576N>=N0
ex:f(n)=n^m+a1n+a0\u7684\u6642\u9593\u8907\u96dc\u5ea6=O(n^m)
ex:f(n)=n(n-1)\/2=(n^2-n)\/2=(n^2)*1\/2-n\/2,n^2\u70ba\u6700\u9ad8\u6b21\u65b9\u9805,\u6642\u9593\u8907\u96dc\u5ea6\u70baO=(n^2) 
o<\/strong>
big O\u53bb\u6389theta\u90e8\u4efd
theta:<\/strong>
\u8907\u96dc\u5ea6\u4e0a\u9650\u548c\u8907\u96dc\u5ea6\u4e0b\u9650\u4e00\u6a23\u6642,ex:theada(N)=big O(N)\u548cbig omega(N)
\u82e5f(N)=theada(g(N))\u6210\u7acb\u6642,\u5247\u5b58\u5728\u4e09\u500b\u5e38\u6578C1,C2,N0,\u4f7f\u5f97C1|g(N)|<=|f(N)|<=C2|g(N)|,\u7576N>=N0
ps:
\u7576\u6642\u9593\u8907\u96dc\u5ea6\u6b63\u597d\u8207\u9019\u500b\u554f\u984c\u7684\u6642\u9593\u8907\u96dc\u5ea6\u4e0b\u9650\u76f8\u540c\u6642,\u4e5f\u7a31\u70baasymptotically optimal algorithm
ps:
\u9664\u975e\u8cc7\u6599\u6578n\u5920\u5927,\u5426\u5247\u8907\u96dc\u5ea6\u7b49\u7d1a\u5c0f\u4e0d\u4e00\u5b9a\u6709\u6548\u7387
ps:
\u8907\u96dc\u5ea6\u7b26\u865f\u4e5f\u88ab\u7a31\u70baasymptotic notations(\u8fd1\u4f3c\u7b26\u865f)<\/p>\n\n\n\n

\u8907\u96dc\u5ea6\u7b49\u7d1a:<\/strong>
\u591a\u9805\u5f0f\u6f14\u7b97\u6cd5\u5247(\u591a\u9805\u5f0f\u8907\u96dc\u5ea6):\u53ef\u884c\u7684\u6f14\u7b97\u6cd5\u5247
(1):\u5e38\u6578\u8907\u96dc\u5ea6\uff0c\u6240\u9700\u6642\u9593\u6c38\u9060\u56fa\u5b9a,ex\u96dc\u6e4a\u8868
(2\u5e95log n):\u5c0d\u8907\u8907\u96dc\u5ea6\uff0c\u6642\u9593\u548c\u8cc7\u6599\u91cf\u6210\u5c0d\u6578\u95dc\u4fc2,ex\u4e8c\u5206\u641c\u5c0b,\u4e8c\u5143\u6a39\u641c\u5c0b,\u8cbb\u5f0f\u641c\u5c0b
(n);\u7dda\u6027\u8907\u96dc\u5ea6,ex:\u5faa\u5e8f\u641c\u5c0b,\u4e8c\u5143\u6a39\u8d70\u8a2a
(n 2\u5e95log n):\u6b21\u7dda\u6027\u8907\u96dc\u5ea6,ex:\u5feb\u901f\u6392\u5217\u6cd5\uff0c\u4e8c\u9805\u5408\u4f75\u6392\u5e8f\u6cd5\uff0c\u5806\u7a4d\u6392\u5e8f\u6cd5
(n^2):\u5e73\u65b9\u8907\u96dc\u5ea6\uff0c\u6642\u9593\u548c\u8cc7\u6599\u91cf\u6210\u5e73\u65b9\u95dc\u4fc2,ex:\u77e9\u9663\u52a0\u6e1b,\u7c21\u55ae\u6392\u5e8f\u6f14\u7b97\u6cd5,\u63d2\u5165\u6392\u5e8f\u6cd5,\u9078\u64c7\u6392\u5e8f\u6cd5,\u6c23\u6ce1\u6392\u5e8f\u6cd5
(n^3):\u7acb\u65b9\u8907\u96dc\u5ea6\uff0cex:\u5169\u500bn*n\u77e9\u9663\u76f8\u4e58
\u6307\u6578\u6f14\u7b97\u6cd5\u5247(\u6307\u6578\u8907\u96dc\u5ea6)\uff1a\u4e0d\u53ef\u884c\u7684\u6f14\u7b97\u6cd5\u5247
(2^n):\u6307\u6578\u8907\u96dc\u5ea6\uff0cex:\u90e8\u4efd\u96c6\u5408\u4e4b\u554f\u984c,\u6cb3\u5167\u5854\u554f\u984c,\u6392\u5217\u554f\u984c
(n!):<\/p>\n\n\n\n

\u8907\u96dc\u5ea6\u8a08\u7b97<\/strong>
theta
1+1+….+1=n=theta(n):\u901a\u5e38\u662f\u4e00\u500b\u8ff4\u5708
1+2+……+n=n(n+1)\/2=theta(n^2)
1^2+2^2+…..+n^2=n(n+1)(2n+1)\/6=theta(n^3)
1^k+2^k+…..+n^k=theta(n^(k+1))
1+1\/2+1\/3+… + 1\/n =theta(lg n)
1+r+r^2+r^3+…+ r^n= (r^(n+1)-1)\/(r-1) =theta(r^n)
bigO
1+2+3+…n < n+n+…n = n^2 = bigO(n^2)
n!=1*2*3*…*n < n*n*…*n = n^n = bigO(n^n)
n*log(n)! = bigO(n*log(n))<\/p>\n\n\n\n

\u5169\u51fd\u6578\u76f8\u52a0\u7684\u8907\u96dc\u5ea6\u7b49\u7d1a\u5224\u65b7<\/strong>
\u539f\u5247:\u5c55\u958b\u7bc4\u570d\u5f8c,\u5728\u53d6\u6700\u5927
ex:
bigO(n)+bigO(n*log(n)) <\/strong>
bigO(n)=[1,n]
bigO(n*log(n))=[1,n*log(n)]
\u53d6\u6700\u5927\u5f97\u5230[1,n*log(n)],\u5c6c\u65bcbigO(n*log(n))
ex:
big_omega(n)+theta(n^2)<\/strong>
big_omega(n)=[n,infinite]
big_theta(n^2)=[n^2,n^2]
\u53d6\u6700\u5927\u5f97\u5230[n^2,infinite],\u5c6c\u65bcbig_omega(n^2)
ex:
theta(n)+bigO(n^2)<\/strong>
theta(n)=[n,n]
bigO=[1,n^2]
\u53d6\u6700\u5927\u5f97\u5230[n,n^2],\u5c6c\u65bcbig_omega(n) and bigO(n^2)<\/p>\n\n\n\n

…………………<\/p>\n\n\n\n

\u554f\u984c\u7684\u5206\u985e
\u4e0d\u53ef\u8a08\u7b97\u7684\u554f\u984c\uff1a\u4e0d\u5b58\u5728\u6709\u89e3\u6c7a\u554f\u984c\u7684\u6f14\u7b97\u6cd5
\u90e8\u4efd\u53ef\u8a08\u7b97\u7684\u554f\u984c\uff1a\u4e0d\u5b58\u5728\u89e3\u6c7a\u554f\u984c\u7684\u6f14\u7b97\u6cd5\uff0c\u5728\u90e8\u4efd\u60c5\u6cc1\u4e0b\u53ef\u5f97\u5230\u7d50\u679c
\u53ef\u8a08\u7b97\u7684\u554f\u984c\uff1a\u6709\u89e3\u6c7a\u554f\u984c\u7684\u6f14\u7b97\u6cd5\uff0c\u542b\u53ef\u884c\u8207\u4e0d\u53ef\u884c<\/p>\n\n\n\n

n,np\u554f\u984c
p\u554f\u984c:
\u53ef\u7528\u6c7a\u5b9a\u6027\u6f14\u7b97\u6cd5(\u4e00\u822c\u7684)\u89e3\u6c7a,\u5c6c\u65bcnp\u554f\u984c(\u56e0\u6c7a\u5b9a\u6027\u6f14\u7b97\u6cd5\u53ef\u8996\u70ba\u975e\u6c7a\u5b9a\u6027\u6f14\u7b97\u6cd5\u4e4b\u7279\u4f8b)
np\u554f\u984c:
\u53ef\u7528\u975e\u6c7a\u5b9a\u6027\u6f14\u7b97\u6cd5(\u53ef\u628a\u8907\u96dcp\u554f\u984c\u8b8a\u5bb9\u6613)\u5728\u591a\u9805\u5f0f\u6642\u9593\u5167\u89e3\u6c7a\u7684\u554f\u984c,
\u5c1a\u672a\u627e\u5230\u591a\u9805\u5f0f\u8907\u96dc\u5ea6\u7684\u6c7a\u5b9a\u6027\u6f14\u7b97\u6cd5\u7684np\u554f\u984c\u6709\uff1a\u6f22\u5f4c\u6566\u8ff4\u8def\u554f\u984c\uff0c\u65c5\u884c\u63a8\u92b7\u54e1\u554f\u984c\uff0c\u6700\u5927\u5b8c\u6574\u5b50\u5716\u554f\u984c<\/p>\n\n\n\n

np-complete\u7406\u8ad6\u5229\u7528\u554f\u984c\u9593\u7684\u6b78\u7d0d\u95dc\u4fc2\u5c07\u554f\u984c\u5206\u6210\uff1a
np-hard\u554f\u984c
np-complete\u554f\u984c:\u6240\u6709np-complete\u554f\u984c,\u90fd\u5c6c\u65bcnp-hard\u554f\u984c  ,ex:\u65c5\u884c\u63a8\u92b7\u54e1<\/p>\n\n\n\n

np-hard\u554f\u984c:
\u5982\u679c\u554f\u984cl\u5c6c\u65bc[np-hard\u554f\u984c]\uff0c\u82e5\u4e14\u70ba\u82e5[\u6eff\u8db3\u554f\u984c]\u53ef\u6b78\u7d0d\u70ba\u554f\u984cl(\u8868\u793a\u70basat\u53ef\u6b78\u7d0d\u70bal)
\u6307\u4e00\u7fa4\u8907\u96dc\u5ea6\u7b49\u7d1a\u4e0d\u5c0f\u65bc’\u6eff\u8db3\u554f\u984c’\u7684\u554f\u984c\uff0c\u5c6c\u65bcnp\u554f\u984c<\/p>\n\n\n\n

np-complete\u554f\u984c:
\u5982\u679c\u554f\u984cL\u662f\u5c6c\u65bc[np-complete\u554f\u984c]\uff0c\u82e5\u4e14\u70ba\u82e5\u554f\u984cL\u662f\u5c6c\u65bc[np-hard\u554f\u984c]\uff0c\u540c\u6642\u554f\u984cL\u4e5f\u662f\u5c6c\u65bc[np\u554f\u984c]<\/p>\n\n\n\n

\u6240\u6709np-complete\u554f\u984c\u90fd\u662f\u76f8\u95dc\u7684\uff0c\u90fd\u9808\u7b26\u5408\u4e0b\u5217\u689d\u4ef6\uff1a
\u5982\u679c\u53ef\u6709\u4e00\u500b[np-complet\u554f\u984c]\u80fd\u5920\u627e\u5230\u591a\u9805\u5f0f\u8907\u96dc\u5ea6\u7684[\u6c7a\u5b9a\u6027\u7684\u6f14\u7b97\u6cd5\u5247]\uff0c\u82e5\u4e14\u70ba\u82e5\u6240\u6709[np-complete\u554f\u984c]\u4e5f\u90fd\u5b58\u5728\u591a\u9805\u5f0f\u8907\u96dc\u5ea6\u7684[\u6c7a\u5b9a\u6027\u6f14\u7b97\u6cd5\u5247]
np-complete\u554f\u984c\u8207np-hard\u554f\u984c\u4e4b\u9593\u4e5f\u5b58\u5728\u4e0b\u5217\u95dc\u4fc2\uff1a
\u5982\u679c\u6709\u4e00\u500b[np-hard\u554f\u984c]\u80fd\u5920\u627e\u5230\u591a\u9805\u5f0f\u8907\u96dc\u5ea6\u7684[\u6c7a\u5b9a\u6027\u7684\u6f14\u7b97\u6cd5\u5247]\uff0c\u5247\u6240\u6709[np-complete\u554f\u984c]\u4e5f\u90fd\u5b58\u5728\u591a\u9805\u5f0f\u8907\u96dc\u5ea6\u7684[\u6c7a\u5b9a\u6027\u7684\u6f14\u7b97\u6cd5\u5247]<\/p>\n","protected":false},"excerpt":{"rendered":"

\u8cc7\u8a0a\u79d1\u5b78\u662f\u63a2\u8a0e\u6f14\u7b97\u6cd5\u5247\u8207\u8cc7\u6599\u7d50\u69cb\u7684\u79d1\u5b78,\u4f7f\u7528\u6700\u9069\u7576\u7684\u8cc7\u6599\u7d50\u69cb …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[15],"tags":[],"class_list":["post-552","post","type-post","status-publish","format-standard","hentry","category-algorithm"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/552","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=552"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/552\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=552"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=552"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}