{"id":994,"date":"2024-07-18T16:27:05","date_gmt":"2024-07-18T16:27:05","guid":{"rendered":"https:\/\/science-hub.click\/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88-%E5%AE%9A%E7%BE%A9\/"},"modified":"2024-07-18T16:27:05","modified_gmt":"2024-07-18T16:27:05","slug":"%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88-%E5%AE%9A%E7%BE%A9","status":"publish","type":"post","link":"https:\/\/science-hub.click\/?p=994","title":{"rendered":"\u633f\u5165\u30bd\u30fc\u30c8 – \u5b9a\u7fa9"},"content":{"rendered":"

\u5c0e\u5165<\/h2>
\n\"\"<\/figure><\/div>

\u633f\u5165\u30bd\u30fc\u30c8<\/b>\u306f\u53e4\u5178\u7684\u306a\u30bd\u30fc\u30c8 \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u3042\u308a\u3001\u305d\u306e\u539f\u7406\u306f\u975e\u5e38\u306b\u5358\u7d14\u3067\u3059\u3002\u3053\u308c\u306f\u3001\u307b\u3068\u3093\u3069\u306e\u4eba\u304c\u30ab\u30fc\u30c9\u3092\u5206\u985e\u3059\u308b\u305f\u3081\u306b\u81ea\u7136\u306b\u4f7f\u7528\u3059\u308b\u4e26\u3079\u66ff\u3048\u3067\u3059\u3002\u30b7\u30e3\u30c3\u30d5\u30eb\u3055\u308c\u305f\u30ab\u30fc\u30c9\u3092 1 \u679a\u305a\u3064\u30c6\u30fc\u30d6\u30eb\u304b\u3089\u53d6\u308a\u51fa\u3057\u3001\u5404\u30ab\u30fc\u30c9\u3092\u6240\u5b9a\u306e\u4f4d\u7f6e\u306b\u633f\u5165\u3057\u3066\u30cf\u30f3\u30c9<\/a><\/span>\u3092\u5f62\u6210\u3057\u307e\u3059\u3002<\/p>

\u4e00\u822c\u306b\u3001\u633f\u5165\u30bd\u30fc\u30c8\u306f\u6f38\u8fd1\u8907\u96d1\u3055<\/a><\/span>\u304c\u4e8c\u6b21\u95a2\u6570\u3067\u3042\u308b\u305f\u3081\u3001\u5927\u898f\u6a21\u306a\u30b7\u30fc\u30b1\u30f3\u30b9\u3092\u51e6\u7406\u3059\u308b\u5834\u5408\u306e\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8<\/a><\/span>\u3084\u30de\u30fc\u30b8<\/a><\/span>\u30bd\u30fc\u30c8\u306a\u3069\u306e\u4ed6\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3088\u308a\u3082\u306f\u308b\u304b\u306b\u9045\u304f\u306a\u308a\u307e\u3059\u3002<\/p>

\u305f\u3060\u3057\u3001\u633f\u5165\u30bd\u30fc\u30c8\u306f\u3001\u5c0f\u3055\u306a\u5165\u529b\u306b\u5bfe\u3057\u3066\u6700\u3082\u52b9\u7387\u7684\u306a\u30bd\u30fc\u30c8\u3067\u3042\u308b\u3068\u8003\u3048\u3089\u308c\u3066\u3044\u307e\u3059\u3002\u30c7\u30fc\u30bf<\/a><\/span>\u304c\u3059\u3067\u306b\u307b\u307c\u30bd\u30fc\u30c8\u3055\u308c\u3066\u3044\u308b\u5834\u5408\u3082\u975e\u5e38\u306b\u9ad8\u901f\u3067\u3059\u3002\u3053\u308c\u3089\u306e\u7406\u7531\u304b\u3089\u3001\u5b9f\u969b\u306b\u306f\u3001\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8 (\u307e\u305f\u306f\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8<\/i>) \u306a\u3069\u306e\u4ed6\u306e\u30e1\u30bd\u30c3\u30c9\u3068\u7d44\u307f\u5408\u308f\u305b<\/span>\u3066\u4f7f\u7528\u200b\u200b\u3055\u308c\u307e\u3059\u3002<\/p>

\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc \u30d7\u30ed\u30b0\u30e9\u30df\u30f3\u30b0<\/a><\/span>\u3067\u306f\u3001\u3053\u306e\u4e26\u3079\u66ff\u3048\u306f\u30c6\u30fc\u30d6\u30eb\u306b\u9069\u7528\u3055\u308c\u308b\u3053\u3068\u304c\u6700\u3082\u591a\u3044\u3067\u3059\u3002\u4ee5\u4e0b\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8aac\u660e\u3068\u691c\u8a0e\u306f\u3053\u306e\u30d0\u30fc\u30b8\u30e7\u30f3\u306b\u9650\u5b9a\u3055\u308c\u307e\u3059\u304c\u3001\u30ea\u30b9\u30c8\u3078\u306e\u9069\u5fdc\u306b\u3064\u3044\u3066\u306f\u5f8c\u3067\u691c\u8a0e\u3057\u307e\u3059\u3002<\/p>

\n\"\u633f\u5165\u30bd\u30fc\u30c8<\/figure>

\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8aac\u660e<\/h2>

\u3053\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u306f\u3001\u30bd\u30fc\u30c8\u5bfe\u8c61\u306e<\/a><\/span>\u914d\u5217\u3092\u6700\u521d\u304b\u3089\u6700\u5f8c\u307e\u3067\u8abf\u3079\u307e\u3059\u3002 i<\/i>\u756a\u76ee\u306e\u8981\u7d20\u3092\u691c\u8a0e\u3059\u308b\u6642\u70b9\u3067\u3001\u305d\u306e\u8981\u7d20\u306b\u5148\u884c\u3059\u308b\u8981\u7d20\u306f\u3059\u3067\u306b\u30bd\u30fc\u30c8\u3055\u308c\u3066\u3044\u307e\u3059\u3002\u30ab\u30fc\u30c9 \u30b2\u30fc\u30e0\u306e\u4f8b\u3067\u4f8b\u3048\u308b\u3068\u3001\u65c5\u306ei<\/i>\u756a\u76ee\u306e\u30b9\u30c6\u30c3\u30d7\u306b\u3044\u308b\u3068\u304d\u3001 i<\/i>\u756a\u76ee\u306e\u8981\u7d20\u306f\u5165\u529b\u3055\u308c\u305f\u30ab\u30fc\u30c9\u3067\u3001\u524d\u306e\u8981\u7d20\u306f\u30bd\u30fc\u30c8\u3055\u308c\u305f\u624b\u672d\u3067\u3001\u6b21\u306e\u8981\u7d20\u306f\u30ab\u30fc\u30c9\u306b\u5bfe\u5fdc\u3057\u307e\u3059\u3002\u307e\u3060\u30c6\u30fc\u30d6\u30eb\u306e\u4e0a\u3067\u30b7\u30e3\u30c3\u30d5\u30eb\u3055\u308c\u3066\u3044\u307e\u3059\u3002<\/p>

\u30b9\u30c6\u30c3\u30d7\u306e\u76ee\u7684\u306f\u3001 i<\/i>\u756a\u76ee\u306e\u8981\u7d20\u3092\u3001\u5148\u884c\u3059\u308b\u8981\u7d20\u306e\u4e2d\u3067\u305d\u306e\u4f4d\u7f6e\u306b\u633f\u5165\u3059\u308b\u3053\u3068\u3067\u3059\u3002\u3053\u308c\u3092\u884c\u3046\u306b\u306f\u3001\u4ed6\u306e\u8981\u7d20\u3068\u6bd4\u8f03\u3057\u3066\u8981\u7d20\u3092\u633f\u5165\u3059\u308b\u5834\u6240\u3092\u898b\u3064\u3051\u3001\u633f\u5165\u3092\u5b9f\u884c\u3067\u304d\u308b\u3088\u3046\u306b\u8981\u7d20\u3092\u30aa\u30d5\u30bb\u30c3\u30c8\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002\u5b9f\u969b\u306b\u306f\u3001\u3053\u308c\u3089 2 \u3064\u306e\u30a2\u30af\u30b7\u30e7\u30f3\u306f 1 \u3064\u306e\u30d1\u30b9\u3067\u5b9f\u884c\u3055\u308c\u308b\u3053\u3068\u304c\u591a\u304f\u3001\u3053\u308c\u306f\u3001\u3088\u308a\u5c0f\u3055\u3044\u8981\u7d20\u306b\u906d\u9047\u3059\u308b\u307e\u3067\u8981\u7d20\u3092\u5f90\u3005\u306b<\/a><\/span>\u300c\u4e0a\u306b\u79fb\u52d5\u300d\u3059\u308b\u3053\u3068\u3067\u69cb\u6210\u3055\u308c\u307e\u3059\u3002<\/p>

\u4ee5\u4e0b\u306f\u3001\u63d0\u793a\u3055\u308c\u305f\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u7591\u4f3c\u30b3\u30fc\u30c9\u306e<\/span>\u8aac\u660e\u3067\u3059\u3002\u30c6\u30fc\u30d6\u30ebT<\/i>\u306e\u8981\u7d20\u306b\u306f 0 \u304b\u3089n<\/i> -1 \u307e\u3067\u306e\u756a\u53f7\u304c\u4ed8\u3051\u3089\u308c\u307e\u3059\u3002<\/p>

 \u30d7\u30ed\u30b7\u30fc\u30b8\u30e3 sort_insertion(array T, integer n) for i from 1 to n - 1 x:= T[i] j = i (j > 0 \u304a\u3088\u3073 T[j - 1] > x T[j] = T[j) - 1] j = j - 1; T[j] = x<\/pre>
\u633f\u5165\u30bd\u30fc\u30c8\u306f\u3001\u5b89\u5b9a\u3057\u305f\u30bd\u30fc\u30c8 (\u7b49\u3057\u3044\u8981\u7d20\u306e\u51fa\u73fe\u9806\u5e8f\u3092\u4fdd\u6301) \u3067\u3042\u308a\u3001\u30a4\u30f3\u30d7\u30ec\u30fc\u30b9 \u30bd\u30fc\u30c8 (\u88dc\u52a9\u914d\u5217\u3092\u4f7f\u7528\u3057\u307e\u305b\u3093) \u3067\u3059\u3002<\/p>
\u8907\u96d1<\/h2>
\u633f\u5165\u30bd\u30fc\u30c8\u306e\u8907\u96d1\u3055\u306f\u3001\u6700\u60aa\u306e\u5834\u5408\u304a\u3088\u3073\u5e73\u5747<\/a><\/span>\u3067 \u0398( n2<\/i> ) \u3067\u3042\u308a\u3001\u6700\u826f\u306e\u5834\u5408<\/sup>\u3067\u306f\u7dda\u5f62\u3067\u3059\u3002\u3088\u308a\u6b63\u78ba\u306b\u306f:<\/p>
  1. \u914d\u5217\u304c\u9006\u65b9\u5411\u306b\u30bd\u30fc\u30c8\u3055\u308c\u308b\u3068\u304d\u306b\u5230\u9054\u3059\u308b\u6700\u60aa\u306e\u30b1\u30fc\u30b9\u3067\u306f\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u7d04n<\/i> 2<\/sup> \/2 \u306e\u4ee3\u5165\u3068\u6bd4\u8f03\u3092\u5b9f\u884c\u3057\u307e\u3059\u3002<\/li>
  2. \u8981\u7d20\u304c\u500b\u5225\u3067\u3042\u308a\u3001\u305d\u308c\u3089\u306e\u9806\u5217\u304c\u3059\u3079\u3066\u7b49\u3057\u3044\u53ef\u80fd\u6027\u304c\u3042\u308b\u5834\u5408\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u5e73\u5747\u3057\u3066\u7d04n<\/i> 2<\/sup> \/4 \u56de\u306e\u5272\u308a\u5f53\u3066\u3068\u6bd4\u8f03\u3092\u5b9f\u884c\u3057\u307e\u3059\u3002<\/li>
  3. \u914d\u5217\u304c\u3059\u3067\u306b\u30bd\u30fc\u30c8\u3055\u308c\u3066\u3044\u308b\u5834\u5408\u3001 n-1 \u56de\u306e<\/i>\u6bd4\u8f03\u3068 O( n<\/i> ) \u56de\u306e\u4ee3\u5165\u304c\u884c\u308f\u308c\u307e\u3059\u3002<\/li><\/ol>
    \u914d\u5217\u304c\u307b\u307c<\/i>\u30bd\u30fc\u30c8\u3055\u308c\u3066\u3044\u308b\u5834\u5408 (\u305f\u3068\u3048\u3070\u3001\u5404\u8981\u7d20\u304c\u672c\u6765\u3042\u308b\u3079\u304d\u4f4d\u7f6e\u304b\u3089\u5236\u9650\u3055\u308c\u305f\u8ddd\u96e2\u306b\u3042\u308b\u5834\u5408\u3001\u307e\u305f\u306f\u5236\u9650\u3055\u308c\u305f\u6570\u5024<\/a><\/span>\u3092\u9664\u304f\u3059\u3079\u3066\u306e\u8981\u7d20\u304c\u6240\u5b9a\u306e\u4f4d\u7f6e\u306b\u3042\u308b\u5834\u5408)\u3001\u633f\u5165\u30bd\u30fc\u30c8\u306e\u8907\u96d1\u3055\u306f\u7dda\u5f62\u306e\u307e\u307e\u3067\u3059\u3002\u3053\u306e\u7279\u5b9a\u306e\u72b6\u6cc1<\/a><\/span>\u3067\u306f\u3001\u633f\u5165\u30bd\u30fc\u30c8\u306f\u4ed6\u306e\u30bd\u30fc\u30c8\u65b9\u6cd5\u3088\u308a\u3082\u512a\u308c\u305f\u30d1\u30d5\u30a9\u30fc\u30de\u30f3\u30b9\u3092\u767a\u63ee\u3057\u307e\u3059\u3002\u305f\u3068\u3048\u3070\u3001\u30de\u30fc\u30b8\u30bd\u30fc\u30c8\u3068\u30af\u30a4\u30c3\u30af\u30bd\u30fc\u30c8\uff08\u30d4\u30dc\u30c3\u30c8\u30e9\u30f3\u30c0\u30e0\u5316\u3092\u4f7f\u7528\uff09\u306f\u4e21\u65b9\u3068\u3082
    $$ {\\Theta(n\\,\\log n)} $$<\/div>\u30bd\u30fc\u30c8\u3055\u308c\u305f\u30ea\u30b9\u30c8\u4e0a\u3067\u3042\u3063\u3066\u3082\u3002<\/p><\/div>
    \n\"\u633f\u5165\u30bd\u30fc\u30c8<\/figure>
    \u53c2\u8003\u8cc7\u6599<\/h2>
    1. \u062a\u0631\u062a\u064a\u0628 \u0628\u0627\u0644\u0625\u062f\u0631\u0627\u062c \u2013 arabe<\/a><\/li>
    2.  \u018flav\u0259 etm\u0259kl\u0259 nizamlama \u2013 azerba\u00efdjanais<\/a><\/li>
    3.  \u0421\u043e\u0440\u0442\u0438\u0440\u0430\u043d\u0435 \u0447\u0440\u0435\u0437 \u0432\u043c\u044a\u043a\u0432\u0430\u043d\u0435 \u2013 bulgare<\/a><\/li>
    4.  \u09b8\u09a8\u09cd\u09a8\u09bf\u09ac\u09c7\u09b6 \u09ac\u09be\u099b\u09be\u0987 \u2013 bengali<\/a><\/li>
    5.  \u0158azen\u00ed vkl\u00e1d\u00e1n\u00edm \u2013 tch\u00e8que<\/a><\/li>
    6.  Inds\u00e6ttelsessortering \u2013 danois<\/a><\/li><\/ol><\/div>\n
      \n 
      \n  \u633f\u5165\u30bd\u30fc\u30c8 – \u5b9a\u7fa9\u30fb\u95a2\u9023\u52d5\u753b\n <\/h2>\n 
      \n  \n  
      \n   
      \n