{"id":20130,"date":"2024-08-24T16:12:09","date_gmt":"2024-08-24T16:12:09","guid":{"rendered":"https:\/\/science-hub.click\/%E3%82%BD%E3%83%BC%E3%83%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC\/"},"modified":"2024-08-24T16:12:09","modified_gmt":"2024-08-24T16:12:09","slug":"%E3%82%BD%E3%83%BC%E3%83%88%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E8%A9%B3%E3%81%97%E3%81%8F%E8%A7%A3%E8%AA%AC","status":"publish","type":"post","link":"https:\/\/science-hub.click\/?p=20130","title":{"rendered":"\u30bd\u30fc\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac"},"content":{"rendered":"<div><div><h2>\u5c0e\u5165<\/h2><p><b>\u30bd\u30fc\u30c8 \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0<\/b>\u306f\u3001\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf \u30b5\u30a4\u30a8\u30f3\u30b9\u307e\u305f\u306f\u6570\u5b66\u306b\u304a\u3044\u3066\u3001\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306e\u30b3\u30ec\u30af\u30b7\u30e7\u30f3\u3092\u7279\u5b9a\u306e\u9806\u5e8f\u3067\u6574\u7406\u3067\u304d\u308b\u3088\u3046\u306b\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u4e26\u3079\u66ff\u3048\u3089\u308c\u308b\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306f\u3001\u9806\u5e8f\u95a2\u4fc2 (\u901a\u5e38\u306f\u5168\u4f53\u306e\u9806\u5e8f) \u3092\u6301\u3064\u30bb\u30c3\u30c8\u306e\u4e00\u90e8\u3067\u3059\u3002\u6700\u3082\u3088\u304f\u4f7f\u7528\u3055\u308c\u308b\u9806\u5e8f\u306f\u3001<span>\u6570\u5024<\/span>\u9806\u5e8f\u3068\u8f9e\u66f8\u7de8\u96c6 (\u8f9e\u66f8) \u9806\u5e8f\u3067\u3059\u3002<\/p><p>\u8003\u616e\u3055\u308c\u308b\u9806\u5e8f\u95a2\u4fc2\u306b\u5fdc\u3058\u3066\u3001\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306e\u540c\u3058\u30b3\u30ec\u30af\u30b7\u30e7\u30f3\u304b\u3089\u3055\u307e\u3056\u307e\u306a\u914d\u7f6e\u304c\u751f\u3058\u308b\u53ef\u80fd\u6027\u304c\u3042\u308a\u307e\u3059\u304c\u3001\u4f7f\u7528\u3055\u308c\u308b\u9806\u5e8f\u95a2\u6570\u3068\u306f\u72ec\u7acb\u3057\u3066<span><a href=\"https:\/\/science-hub.click\/?p=20130\">\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092<\/a><\/span>\u5b9a\u7fa9\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002\u3053\u308c\u306f\u3001\u30b3\u30ec\u30af\u30b7\u30e7\u30f3\u5185\u306e\u8981\u7d20\u306e<span><a href=\"https:\/\/science-hub.click\/?p=95765\">\u4efb\u610f<\/a><\/span>\u306e\u30da\u30a2\u3092\u6bd4\u8f03\u3067\u304d\u308b\u3088\u3046\u306b\u3059\u308b\u9806\u5e8f\u95a2\u4fc2\u306b\u5bfe\u5fdc\u3059\u308b\u7279\u5b9a\u306e\u9806\u5e8f\u95a2\u6570\u306e\u307f\u3092\u4f7f\u7528\u3057\u307e\u3059\u3002<\/p><figure class=\"wp-block-image size-large is-style-default\">\n<img decoding=\"async\" alt=\"\u30bd\u30fc\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\" class=\"aligncenter\" onerror=\"this.style.display=none;\" src=\"https:\/\/img.youtube.com\/vi\/R9LkFlZz4Bc\/0.jpg\" style=\"width:100%;\"\/><\/figure><h2>\u5206\u985e<\/h2><p><span><a href=\"https:\/\/science-hub.click\/?p=84761\">\u30bd\u30fc\u30c8<\/a><\/span>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5206\u985e\u306f\u3001\u305d\u308c\u306b\u3088\u3063\u3066\u8ab2\u305b\u3089\u308c\u308b\u5236\u7d04\u3092\u8003\u616e\u3057\u306a\u304c\u3089\u3001\u5bfe\u51e6\u3059\u308b\u554f\u984c\u306b\u6700\u9069\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u9078\u629e\u3067\u304d\u308b\u305f\u3081\u3001\u975e\u5e38\u306b\u91cd\u8981\u3067\u3059\u3002<\/p><p>\u307e\u305a\u7b2c\u4e00\u306b\u3001\u8981\u7d20\u306e\u30da\u30a2\u9593\u306e\u6bd4\u8f03\u306b\u3088\u3063\u3066\u9032\u884c\u3059\u308b\u4e00\u822c\u7684\u306a\u30a2\u30d7\u30ea\u30b1\u30fc\u30b7\u30e7\u30f3\u306e\u30bd\u30fc\u30c8 \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u3001\u5165\u529b\u30c7\u30fc\u30bf\u306e\u69cb\u9020\u306b\u3064\u3044\u3066\u9650\u5b9a\u7684\u306a\u4eee\u8aac\u3092\u7acb\u3066\u308b\u3088\u308a\u7279\u6b8a\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 (\u305f\u3068\u3048\u3070\u3001\u30c7\u30fc\u30bf\u304c\u53d6\u5f97\u3055\u308c\u305f\u5834\u5408\u306b\u306e\u307f\u9069\u7528\u3067\u304d\u308b\u30ab\u30a6\u30f3\u30c8\u306b\u3088\u308b\u30bd\u30fc\u30c8\u306a\u3069) \u3092\u533a\u5225\u3057\u307e\u3059\u3002\u4e8b\u524d\u306b\u77e5\u3089\u308c\u3066\u3044\u308b\u5c0f\u3055\u306a<span><a href=\"https:\/\/science-hub.click\/?p=57227\">\u30bb\u30c3\u30c8<\/a><\/span>\u304b\u3089\uff09\u3002\u4f55\u3082\u6307\u5b9a\u3057\u306a\u3044\u5834\u5408\u3001\u901a\u5e38\u3001\u300c\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u300d\u3068\u306f\u3001\u6bd4\u8f03\u306b\u3088\u308b\u4e00\u822c\u7684\u306a\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u610f\u5473\u3057\u307e\u3059\u3002<\/p><p>\u30bd\u30fc\u30c8 \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5dee\u5225\u5316\u3092\u53ef\u80fd\u306b\u3059\u308b\u4e3b\u306a\u7279\u5fb4\u306f\u3001<span><a href=\"https:\/\/science-hub.click\/?p=83805\">\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e<\/a><\/span><span><a href=\"https:\/\/science-hub.click\/?p=38628\">\u8907\u96d1\u3055<\/a><\/span>\u3001\u5fc5\u8981\u306a\u30ea\u30bd\u30fc\u30b9 (\u7279\u306b\u4f7f\u7528\u3055\u308c\u308b<span><a href=\"https:\/\/science-hub.click\/?p=40158\">\u30e1\u30e2\u30ea<\/a><\/span>\u9818\u57df\u306e\u70b9)\u3001\u304a\u3088\u3073\u5b89\u5b9a\u3057\u305f\u6027\u8cea\u3067\u3059\u3002<\/p><figure class=\"wp-block-image size-large is-style-default\">\n<img decoding=\"async\" alt=\"\u30bd\u30fc\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\" class=\"aligncenter\" onerror=\"this.style.display=none;\" src=\"https:\/\/img.youtube.com\/vi\/A1UuoXNoy2w\/0.jpg\" style=\"width:100%;\"\/><\/figure><h3><span>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8907\u96d1\u3055<\/span><\/h3><ul><li><i>\u6700\u60aa\u306e\u5834\u5408\u306e<\/i>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u6642\u9593\u8a08\u7b97\u91cf\u306b\u3088\u308a\u3001 <i>n<\/i>\u500b\u306e\u8981\u7d20\u306e\u30bb\u30c3\u30c8\u3092\u4e26\u3079\u66ff\u3048\u308b\u306e\u306b\u5fc5\u8981\u306a\u64cd\u4f5c\u306e<span><a href=\"https:\/\/science-hub.click\/?p=71097\">\u6570<\/a><\/span>\u306b\u4e0a\u9650\u3092\u8a2d\u5b9a\u3059\u308b\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002<\/li><li>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5e73\u5747\u6642\u9593\u8a08\u7b97\u91cf: \u3053\u308c\u306f\u3001\u8981\u7d20\u306e\u30b3\u30ec\u30af\u30b7\u30e7\u30f3\u3092\u4e26\u3079\u66ff\u3048\u308b\u305f\u3081\u306b<i>\u5e73\u5747\u3057\u3066<\/i>\u5b9f\u884c\u3055\u308c\u308b\u57fa\u672c\u64cd\u4f5c\u306e\u6570\u3067\u3059\u3002\u3053\u308c\u306b\u3088\u308a\u3001\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u6bd4\u8f03\u3067\u304d\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u5fc5\u8981\u306a\u5b9f\u884c<span><a href=\"https:\/\/science-hub.click\/?p=82055\">\u6642\u9593<\/a><\/span>\u306b\u3064\u3044\u3066\u306e\u9069\u5207\u306a\u30a2\u30a4\u30c7\u30a2\u304c\u5f97\u3089\u308c\u307e\u3059\u3002\u304b\u306a\u308a\u9ad8\u3044\u7cbe\u5ea6\u3067\u63a8\u5b9a\u3067\u304d\u307e\u3059\u3002\u305f\u3060\u3057\u3001\u30bd\u30fc\u30c8\u3055\u308c\u308b\u30bb\u30c3\u30c8\u304c\u7279\u5b9a\u306e\u5f62\u72b6\u3092\u6301\u3061\u3001 <i>n <b>!<\/b><\/i>\u3092\u8868\u3057\u3066\u3044\u306a\u3044\u5834\u5408\u306f\u3001\u53ef\u80fd\u306a\u7d44\u307f\u5408\u308f\u305b\u3092\u7d44\u307f\u5408\u308f\u305b\u305f\u5834\u5408\u3001\u30d1\u30d5\u30a9\u30fc\u30de\u30f3\u30b9\u306f\u300c\u5e73\u5747\u7684\u306a\u300d\u8907\u96d1\u3055\u3088\u308a\u3082\u306f\u308b\u304b\u306b\u4f4e\u3044\u3001\u307e\u305f\u306f\u306f\u308b\u304b\u306b\u9ad8\u3044\u53ef\u80fd\u6027\u304c\u3042\u308a\u307e\u3059\u3002<\/li><li>\u7a7a\u9593\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u8907\u96d1\u3055 (\u5e73\u5747\u307e\u305f\u306f\u6700\u60aa\u306e\u5834\u5408) \u306f\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u5fc5\u8981\u3068\u3059\u308b\u30e1\u30e2\u30ea\u4f7f\u7528\u91cf\u3092\u8868\u3057\u307e\u3059\u3002\u3053\u308c\u306f\u3001\u5b9f\u884c\u6642\u9593\u3068\u540c\u69d8\u306b\u3001\u4e26\u3079\u66ff\u3048\u308b\u8981\u7d20\u306e\u6570\u306b\u4f9d\u5b58\u3059\u308b\u53ef\u80fd\u6027\u304c\u3042\u308a\u307e\u3059\u3002<\/li><\/ul><p>\u4e00\u822c\u306b<i>T<\/i>\u3067\u8868\u3055\u308c\u308b\u8907\u96d1\u3055\u306f\u3001\u30e9\u30f3\u30c0\u30a6\u8868\u8a18<b>O<\/b>\u304a\u3088\u3073<b>\u0398 \u3092<\/b>\u4f7f\u7528\u3057\u3066\u8981\u7d20\u306e\u6570<i>n<\/i>\u306e\u95a2\u6570\u3068\u3057\u3066\u8868\u3055\u308c\u307e\u3059\u3002\u6700\u3082\u5358\u7d14\u306a\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u4e00\u90e8\u306e\u5834\u5408\u306f T( <i>n<\/i> ) = O( <i>n<\/i> <sup>2<\/sup> )\u3001\u3088\u308a\u8907\u96d1\u306a\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5834\u5408\u306f T( <i>n<\/i> ) = O( <i>n<\/i> \u00b7log( <i>n<\/i> )) \u3067\u3059\u3002<\/p><p>\u6bd4\u8f03\u95a2\u6570\u306b\u57fa\u3065\u304f\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u5e73\u5747\u6642\u9593\u8a08\u7b97\u91cf\u3068\u6700\u60aa\u306e\u5834\u5408\u306e\u6642\u9593\u8a08\u7b97\u91cf\u306f<b>\u3001 <i>n<\/i> \u00b7log( <i>n<\/i> )<\/b>\u3088\u308a\u3082\u512a\u308c\u3066\u3044\u308b\u306f\u305a\u304c\u306a\u3044\u3053\u3068\u304c\u308f\u304b\u308a\u307e\u3059\u3002\u5e73\u5747\u3057\u3066<i>n<\/i> \u00b7log( <i>n<\/i> ) \u56de\u306e\u6bd4\u8f03\u306e\u307f\u3092\u5fc5\u8981\u3068\u3059\u308b\u4e26\u3079\u66ff\u3048\u306f\u3001\u6700\u9069\u3068\u547c\u3070\u308c\u307e\u3059\u3002<\/p><div align=\"left\"><div title=\"[\u62e1\u5927\u3059\u308b]\"><div align=\"left\"><p>\u30bd\u30fc\u30c8\u554f\u984c\u306f\u3001<i>\u5b8c\u5168<\/i><span><a href=\"https:\/\/science-hub.click\/?p=24014\">\u306b\u9806\u5e8f\u4ed8\u3051\u3089\u308c\u305f<\/a><\/span><i>\u96c6\u5408<\/i><i>(<\/i><i>\u4f8b<\/i>: <div class=\"math-formual notranslate\">$$ {\\mathbb{N}} $$<\/div> )\u3001\u6b21\u306e\u3088\u3046\u306b 1, &#8230;, <i>n<\/i>\u306e\u9806\u5217 \u03c3 \u3092\u6c7a\u5b9a\u3057\u307e\u3059: <i>y<\/i> = ( <i>u<\/i> , <i>u<\/i> , &#8230;, <i>u<\/i> ) \u304c\u30bd\u30fc\u30c8\u3055\u308c\u307e\u3059\u3002\u7c21\u5358\u306b\u3059\u308b\u305f\u3081\u306b\u3001\u8981\u7d20\u304c\u500b\u5225\u3067\u3042\u308b\u3068\u4eee\u5b9a\u3057\u307e\u3059\u3002\u3053\u308c\u306b\u3088\u308a\u3001\u9806\u5217 \u03c3 \u306f\u4e00\u610f\u306b\u306a\u308a\u307e\u3059\u3002\u4e00\u822c\u7684\u306a\u30b1\u30fc\u30b9\u3067\u306f\u3001\u7d50\u679c\u306f<i>\u4f9d\u7136\u3068\u3057\u3066<\/i>\u771f\u3067\u3059\u3002<\/p><p>\u9023\u7d9a\u7684\u306a\u6bd4\u8f03\u306b\u3088\u308b\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u30d0\u30a4\u30ca\u30ea<span><a href=\"https:\/\/science-hub.click\/?p=3544\">\u30c4\u30ea\u30fc<\/a><\/span>\u3068\u3057\u3066\u30e2\u30c7\u30eb\u5316\u3055\u308c\u3001\u30c4\u30ea\u30fc\u306e\u5404\u30ce\u30fc\u30c9\u306f\u30bb\u30c3\u30c8\u306e 2 \u3064\u306e\u8981\u7d20\u9593\u306e\u6bd4\u8f03\u306b\u5bfe\u5fdc\u3057\u307e\u3059\u3002 2 \u3064\u306e\u8981\u7d20<i>u<\/i>\u3068<i>u \u3092<\/i>\u6bd4\u8f03\u3057\u3001\u7d50\u679c\u306b\u5fdc\u3058\u3066\u6b21\u306e 2 \u3064\u306e\u30ce\u30fc\u30c9\u306e\u3044\u305a\u308c\u304b\u306b\u79fb\u52d5\u3057\u3001\u305d\u3053\u3067\u5225\u306e\u6bd4\u8f03\u3092\u5b9f\u884c\u3057\u307e\u3059\u3002\u30c4\u30ea\u30fc\u306e\u5404<span><a href=\"https:\/\/science-hub.click\/?p=59557\">\u30ea\u30fc\u30d5<\/a><\/span>(\u7d42\u7aef\u30ce\u30fc\u30c9) \u306f\u3001\u5b8c\u5168\u306b\u30bd\u30fc\u30c8\u3055\u308c\u305f\u30b7\u30fc\u30b1\u30f3\u30b9\u306b\u5bfe\u5fdc\u3057\u307e\u3059\u3002<\/p><p>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u30b7\u30fc\u30b1\u30f3\u30b9\u306e\u9805\u306e\u7f6e\u63db\u306e\u53ef\u80fd\u6027\u3092\u3059\u3079\u3066\u63d0\u4f9b\u3067\u304d\u306a\u3051\u308c\u3070\u306a\u308a\u307e\u305b\u3093\u3002\u3053\u308c\u306f\u3001\u7f6e\u63db \u03c3 \u3092\u63d0\u4f9b\u3059\u308b\u3053\u3068\u3068\u3001\u30bd\u30fc\u30c8\u3055\u308c\u305f\u30b7\u30fc\u30b1\u30f3\u30b9<i>y \u3092<\/i>\u63d0\u4f9b\u3059\u308b\u3053\u3068\u3068\u540c\u7b49\u3067\u3042\u308b\u305f\u3081\u3067\u3059\u3002 <i>n<\/i>\u500b\u306e\u8981\u7d20\u306e\u9806\u5217\u306e\u6570\u306f<i>n <b>!<\/b><\/i> (n \u968e\u4e57) \u30c4\u30ea\u30fc\u4e0a\u306e\u8449\u306e\u6570\u306f\u5c11\u306a\u304f\u3068\u3082<i>n \u3067\u306a\u3051\u308c\u3070\u306a\u308a\u307e\u305b\u3093<b>\u3002<\/b><\/i> \u3002<\/p><p><b>\u6700\u60aa\u306e\u5834\u5408\u306e\u8907\u96d1\u3055\u306e\u4e0b\u9650<\/b><\/p><p><i>h \u304c<\/i>\u30c4\u30ea\u30fc\u306e\u6700\u5927\u306e\u6df1\u3055\u3092\u8868\u3059\u3082\u306e\u3068\u3057\u307e\u3059 (<i>\u6700\u60aa\u306e\u5834\u5408\u306e<\/i>\u30b9\u30c6\u30c3\u30d7\u6570\u306b\u3064\u3044\u3066\u8a71\u3057\u3066\u3044\u307e\u3059)\u3002\u6700\u5927\u6df1\u3055<i>h<\/i>\u306e\u4e8c\u5206\u6728\u306e\u6700\u5927\u8449\u6570\u306f<span>2 <sup><i>h<\/i><\/sup><\/span>\u3067\u3059\u3002<\/p><p>\u3057\u305f\u304c\u3063\u3066\u3001\u6b21\u306e\u3088\u3046\u306b\u306a\u308a\u307e\u3059\u3002 <div class=\"math-formual notranslate\">$$ {2^h \\geq n!} $$<\/div> \u3002\u30b9\u30bf\u30fc\u30ea\u30f3\u30b0\u306e\u516c\u5f0f\u3092\u4f7f\u7528\u3059\u308b\u3068\u3001\u6f38\u8fd1\u7684\u306b\u6b21\u306e\u3088\u3046\u306b\u306a\u308a\u307e\u3059\u3002 <div class=\"math-formual notranslate\">$$ {h \\geq n \\cdot \\log_2(n) &#8211; n \/ \\ln 2 = \\Theta(n\\,\\log n)} $$<\/div> \u3002<\/p><p>\u7a2e\u985e\u304c\u3042\u308b\u3068\u3044\u3046\u4e8b\u5b9f<div class=\"math-formual notranslate\">$$ {n \\cdot \\log_2(n)} $$<\/div>\u4e00\u65b9\u3001\u6f38\u8fd1\u7684\u306b\u6b21\u306e\u3053\u3068\u304c\u53ef\u80fd\u3067\u3042\u308b\u3053\u3068\u3092\u793a\u3057\u3066\u3044\u307e\u3059\u3002 <div class=\"math-formual notranslate\">$$ {h \\leq n \\cdot \\log_2(n)} $$<\/div> \u3002\u3057\u305f\u304c\u3063\u3066\u3001\u3053\u306e\u5883\u754c\u306f\u3001\u6bd4\u8f03\u306b\u3088\u308b\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u6700\u60aa\u306e\u5834\u5408\u306e\u8907\u96d1\u3055\u3092\u6700\u5c0f\u9650\u306b\u6291\u3048\u307e\u3059\u3002<\/p><p><b>\u5e73\u5747\u7684\u306a\u8907\u96d1\u3055\u306e\u4e0b\u9650<\/b><\/p><p>\u4e8c\u5206\u6728<i>A<\/i>\u304c\u4e0e\u3048\u3089\u308c\u305f\u5834\u5408\u3001 <i>A<\/i>\u306e\u8449\u306e\u5e73\u5747\u6df1\u3055\u3092<i>F<\/i> ( <i>A<\/i> ) \u3067\u8868\u3057\u307e\u3059\u3002\u5165\u529b\u8981\u7d20\u306e\u3059\u3079\u3066\u306e\u9806\u5217\u306e\u53ef\u80fd\u6027\u304c\u7b49\u3057\u3044\u5834\u5408\u3001\u6bd4\u8f03\u30c4\u30ea\u30fc<i>A<\/i>\u3068\u306e\u30bd\u30fc\u30c8\u306e\u6bd4\u8f03\u306e\u5e73\u5747\u6570\u306f<i>F<\/i> ( <i>A<\/i> ) \u306b\u7b49\u3057\u304f\u306a\u308a\u307e\u3059\u3002<\/p><p>\u56fa\u5b9a\u6570\u306e\u30ce\u30fc\u30c9\u306e\u5834\u5408\u3001 <i>F<\/i>\u3092\u6700\u5c0f\u5316\u3059\u308b\u30c4\u30ea\u30fc\u306f\u5b8c\u5168\u306a 2 \u5206\u30c4\u30ea\u30fc (\u3064\u307e\u308a\u3001\u8449\u304c\u3059\u3079\u3066\u6700\u5f8c\u307e\u305f\u306f\u6700\u5f8c\u304b\u3089 2 \u756a\u76ee\u306e\u30ec\u30d9\u30eb\u306b\u3042\u308b\u3082\u306e) \u3067\u3059\u3002\u5b9f\u969b\u3001\u4e0d\u5b8c\u5168\u306a\u30c4\u30ea\u30fc<i>A<\/i>\u306b\u306f\u3001\u6df1\u3055<i>h<\/i>\u306e\u8449\u3068\u6700\u5927\u3067\u3082\u6df1\u3055<i>h<\/i> -2 \u306e\u8449\u304c\u5b58\u5728\u3057\u307e\u3059\u3002\u6700\u521d\u306e\u8449\u3092<span><a href=\"https:\/\/science-hub.click\/?p=68283\">2 \u756a\u76ee\u306e<\/a><\/span>\u8449\u306b\u63a5\u7d9a\u3059\u308b\u3068\u3001 <i>F<\/i> ( <i>A&#8217;<\/i> ) &lt; <i>F<\/i> ( <i>A<\/i> ) \u3068\u306a\u308b\u6728<i>A&#8217; \u304c<\/i>\u5f97\u3089\u308c\u307e\u3059\u3002<\/p><p>\u95a2\u6570<i>F \u306f<\/i>\u3001 <i>n<\/i> ! \u3092\u542b\u3080\u3059\u3079\u3066\u306e\u5b8c\u5168\u306a\u30d0\u30a4\u30ca\u30ea \u30c4\u30ea\u30fc\u3067\u540c\u3058\u5024\u3092\u6301\u3061\u307e\u3059\u3002\u8449\u3001 <i>A \u3092<\/i>\u305d\u306e\u3046\u3061\u306e 1 \u3064\u3068\u3057\u3066\u3001\u305d\u306e<span><a href=\"https:\/\/science-hub.click\/?p=58663\">\u9ad8\u3055<\/a><\/span><i>\u306b<\/i>\u6ce8\u76ee\u3057\u3066\u307f\u307e\u3057\u3087\u3046\u3002\u3059\u3079\u3066\u306e\u8449\u306e\u6df1\u3055\u306f\u5c11\u306a\u304f\u3068\u3082<i>h<\/i> -1 \u3067\u3042\u308b\u305f\u3081\u3001\u8449\u306e\u5e73\u5747\u6df1\u3055\u306f\u5c11\u306a\u304f\u3068\u3082<div class=\"math-formual notranslate\">$$ {h-1 = \\Omega(n\\,\\log n)} $$<\/div> (\u3053\u3053\u3067\u3082\u30d7\u30ed\u30d1\u30c6\u30a3 2 <sup>h<\/sup> \u2265 <i>n<\/i>\u3092\u4f7f\u7528\u3057\u307e\u3059!)\u3002<\/p><\/div><\/div><\/div><p>\u305f\u3060\u3057\u3001\u7279\u5b9a\u306e\u7a2e\u985e\u306e\u30c7\u30fc\u30bf (\u6574\u6570\u3001\u30b5\u30a4\u30ba\u304c\u5236\u9650\u3055\u308c\u305f\u6587\u5b57\u5217) \u306b\u3064\u3044\u3066\u306f\u3001<span><a href=\"https:\/\/science-hub.click\/?p=44540\">\u30ab\u30a6\u30f3\u30c8 \u30bd\u30fc\u30c8<\/a><\/span>\u3084\u57fa\u6570\u306b\u3088\u308b\u30bd\u30fc\u30c8\u306a\u3069\u3001\u5b9f\u884c\u6642\u9593\u306e\u70b9\u3067\u3088\u308a\u52b9\u7387\u7684\u306a\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u3042\u308a\u307e\u3059\u3002\u3053\u308c\u3089\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u8981\u7d20\u9593\u306e\u6bd4\u8f03\u3092\u4f7f\u7528\u3057\u307e\u305b\u3093 (\u3057\u305f\u304c\u3063\u3066\u3001 <i>n\u30fblog(n)<\/i>\u9650\u754c\u306f\u305d\u308c\u3089\u306b\u9069\u7528\u3055\u308c\u307e\u305b\u3093) \u304c\u3001\u4e26\u3079\u66ff\u3048\u3089\u308c\u308b\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306b\u3064\u3044\u3066\u306e\u4eee\u5b9a\u3092\u5fc5\u8981\u3068\u3057\u307e\u3059\u3002\u305f\u3068\u3048\u3070\u3001\u30ab\u30a6\u30f3\u30c8 \u30bd\u30fc\u30c8\u3068\u57fa\u6570\u306b\u3088\u308b\u30bd\u30fc\u30c8\u306f\u3001\u30bb\u30c3\u30c8 [1, <i>m<\/i> ] \u306b\u5c5e\u3059\u308b\u3053\u3068\u304c\u308f\u304b\u3063\u3066\u3044\u308b\u6574\u6570\u306b\u9069\u7528\u3055\u308c\u307e\u3059\u3002\u57fa\u6570\u306b\u3088\u308b\u30bd\u30fc\u30c8\u3067\u306f\u3001 <i>m \u304c<\/i>2 \u306e<span><a href=\"https:\/\/science-hub.click\/?p=15958\">\u7d2f\u4e57<\/a><\/span>(c &#8216;\u3001\u3064\u307e\u308a 2 \u306e\u5f62\u5f0f\u3067\u3042\u308b) \u3068\u3044\u3046\u8ffd\u52a0\u306e\u4eee\u5b9a\u304c\u9069\u7528\u3055\u308c\u307e\u3059\u3002 <sup>k<\/sup> )\u3002<\/p><h3><span>\u6240\u5b9a\u306e\u4f4d\u7f6e\u306b\u3042\u308b\u30ad\u30e3\u30e9\u30af\u30bf\u30fc<\/span><\/h3><p>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u975e\u5e38\u306b\u9650\u3089\u308c\u305f\u6570\u306e\u5909\u6570\u306e\u307f\u3092\u4f7f\u7528\u3057\u3001<span><a href=\"https:\/\/science-hub.click\/?p=107393\">\u4e26\u3079\u66ff\u3048\u3066<\/a><\/span>\u3044\u308b\u69cb\u9020\u3092\u76f4\u63a5\u5909\u66f4\u3059\u308b\u5834\u5408\u306b\u3001\u9069\u5207\u306b\u914d\u7f6e\u3055\u308c\u3066\u3044\u308b\u3068\u8a00\u308f\u308c\u307e\u3059\u3002\u3053\u308c\u306b\u306f\u3001\u9069\u5207\u306a<span><a href=\"https:\/\/science-hub.click\/?p=25552\">\u30c7\u30fc\u30bf<\/a><\/span>\u69cb\u9020 (<span><a href=\"https:\/\/science-hub.click\/?p=26304\">\u30c6\u30fc\u30d6\u30eb<\/a><\/span>\u306a\u3069) \u3092\u4f7f\u7528\u3059\u308b\u5fc5\u8981\u304c\u3042\u308a\u307e\u3059\u3002\u4f7f\u7528\u53ef\u80fd\u306a\u30e1\u30e2\u30ea\u304c<span><a href=\"https:\/\/science-hub.click\/?p=3678\">\u5927\u91cf\u306b<\/a><\/span>\u306a\u3044\u5834\u5408\u3001\u3053\u306e\u6587\u5b57\u306f\u975e\u5e38\u306b\u91cd\u8981\u306b\u306a\u308a\u307e\u3059\u3002<\/p><p>\u305f\u3060\u3057\u3001\u4e00\u822c\u306b\u3001\u30c7\u30fc\u30bf\u81ea\u4f53\u3092\u76f4\u63a5\u4e26\u3079\u66ff\u3048\u308b\u306e\u3067\u306f\u306a\u304f\u3001\u30c7\u30fc\u30bf\u3078\u306e\u53c2\u7167 (\u307e\u305f\u306f\u30dd\u30a4\u30f3\u30bf) \u306e\u307f\u3092\u4e26\u3079\u66ff\u3048\u308b\u3053\u3068\u306b\u6ce8\u610f\u3057\u3066\u304f\u3060\u3055\u3044\u3002<\/p><figure class=\"wp-block-image size-large is-style-default\">\n<img decoding=\"async\" alt=\"\u30bd\u30fc\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\" class=\"aligncenter\" onerror=\"this.style.display=none;\" src=\"https:\/\/img.youtube.com\/vi\/Gho8e9c6RAM\/0.jpg\" style=\"width:100%;\"\/><\/figure><h3><span>\u5b89\u5b9a\u3057\u305f\u6027\u683c<\/span><\/h3><p>\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u9806\u5e8f\u95a2\u4fc2\u306b\u304a\u3044\u3066\u7b49\u3057\u3044\u91cf\u306e\u76f8\u5bfe\u9806\u5e8f\u3092\u7dad\u6301\u3059\u308b\u5834\u5408\u306b\u5b89\u5b9a\u3057\u3066\u3044\u308b\u3068\u8a00\u308f\u308c\u307e\u3059\u3002<\/p><p>\u305f\u3068\u3048\u3070\u3001\u6b21\u306e\u4e00\u9023\u306e\u8981\u7d20\u3092\u8003\u3048\u3066\u307f\u307e\u3059\u3002<\/p><pre> (4, 1) (3, 1) (3, 7) (5, 6)<\/pre><p>\u6700\u521d\u306e\u5ea7\u6a19 (\u30ad\u30fc) \u306b\u57fa\u3065\u3044\u3066\u4e26\u3079\u66ff\u3048\u308b\u3068\u3001\u76f8\u5bfe\u9806\u5e8f\u304c\u5c0a\u91cd\u3055\u308c\u308b\u5834\u5408\u3068\u305d\u3046\u3067\u306a\u3044\u5834\u5408\u306e 2 \u3064\u306e\u30b1\u30fc\u30b9\u304c\u8003\u3048\u3089\u308c\u307e\u3059\u3002<\/p><pre> (3, 1) (3, 7) (4, 1) (5, 6) (\u76f8\u5bfe\u9806\u5e8f\u7dad\u6301) (3, 7) (3, 1) (4, 1) (5, 6) (\u76f8\u5bfe\u9806\u5e8f\u5909\u66f4)<\/pre><p> 2 \u3064\u306e\u8981\u7d20<i>\u306e\u9806\u5e8f\u95a2\u4fc2\u304c<\/i>\u7b49\u3057\u3044 (\u3064\u307e\u308a\u3001\u540c\u3058\u30ad\u30fc\u3092\u6301\u3064) \u5834\u5408\u3001\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u3053\u308c\u3089 2 \u3064\u306e\u8981\u7d20\u304c\u5b9f\u884c\u3055\u308c\u308b\u524d\u306e\u9806\u5e8f\u3092\u7dad\u6301\u3057\u307e\u3059\u3002\u4e0d\u5b89\u5b9a\u306a\u4e26\u3079\u66ff\u3048\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u5b89\u5b9a\u3055\u305b\u308b\u305f\u3081\u306b\u7279\u5225\u306b\u518d\u52a0\u5de5\u3059\u308b\u3053\u3068\u306f\u3067\u304d\u307e\u3059\u304c\u3001\u3053\u308c\u306b\u3088\u308a\u901f\u5ea6\u304c\u72a0\u7272\u306b\u306a\u3063\u305f\u308a\u3001\u8ffd\u52a0\u306e\u30e1\u30e2\u30ea\u9818\u57df\u304c\u5fc5\u8981\u306b\u306a\u3063\u305f\u308a\u3059\u308b\u53ef\u80fd\u6027\u304c\u3042\u308a\u307e\u3059\u3002<\/p><p>\u4ee5\u4e0b\u306b\u6319\u3052\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u4e2d\u3067\u5b89\u5b9a\u3057\u3066\u3044\u308b\u30bd\u30fc\u30c8\u306f\u3001\u30d0\u30d6\u30eb \u30bd\u30fc\u30c8\u3001\u633f\u5165\u30bd\u30fc\u30c8\u3001<span><a href=\"https:\/\/science-hub.click\/?p=32314\">\u30de\u30fc\u30b8<\/a><\/span>\u30bd\u30fc\u30c8\u3067\u3059\u3002\u4ed6\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u306f\u3001\u8981\u7d20\u306e\u521d\u671f\u9806\u5e8f\u3092\u4fdd\u5b58\u3059\u308b\u305f\u3081\u306b O(n) \u500b\u306e\u8ffd\u52a0\u30e1\u30e2\u30ea\u304c\u5fc5\u8981\u3067\u3059\u3002<\/p><\/div><h2 class=\"ref_link\">\u53c2\u8003\u8cc7\u6599<\/h2><ol><li><a class=\"notranslate\" href=\"https:\/\/ar.wikipedia.org\/wiki\/%D8%AE%D9%88%D8%A7%D8%B1%D8%B2%D9%85%D9%8A%D8%A9_%D8%AA%D8%B1%D8%AA%D9%8A%D8%A8\">\u062e\u0648\u0627\u0631\u0632\u0645\u064a\u0629 \u062a\u0631\u062a\u064a\u0628 \u2013 arabe<\/a><\/li><li> <a class=\"notranslate\" href=\"https:\/\/az.wikipedia.org\/wiki\/Nizamlama_alqoritmi\">Nizamlama alqoritmi \u2013 azerba\u00efdjanais<\/a><\/li><li> <a class=\"notranslate\" href=\"https:\/\/bg.wikipedia.org\/wiki\/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D1%8A%D0%BC_%D0%B7%D0%B0_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%B0%D0%BD%D0%B5\">\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u044a\u043c \u0437\u0430 \u0441\u043e\u0440\u0442\u0438\u0440\u0430\u043d\u0435 \u2013 bulgare<\/a><\/li><li> <a class=\"notranslate\" href=\"https:\/\/bn.wikipedia.org\/wiki\/%E0%A6%B8%E0%A6%B0%E0%A7%8D%E0%A6%9F%E0%A6%BF%E0%A6%82_%E0%A6%85%E0%A7%8D%E0%A6%AF%E0%A6%BE%E0%A6%B2%E0%A6%97%E0%A7%8B%E0%A6%B0%E0%A6%BF%E0%A6%A6%E0%A6%AE\">\u09b8\u09b0\u09cd\u099f\u09bf\u0982 \u0985\u09cd\u09af\u09be\u09b2\u0997\u09cb\u09b0\u09bf\u09a6\u09ae \u2013 bengali<\/a><\/li><li> <a class=\"notranslate\" href=\"https:\/\/ca.wikipedia.org\/wiki\/Algorisme_d%27ordenaci%C3%B3\">Algorisme d&#8217;ordenaci\u00f3 \u2013 catalan<\/a><\/li><li> <a class=\"notranslate\" href=\"https:\/\/cs.wikipedia.org\/wiki\/%C5%98adic%C3%AD_algoritmus\">\u0158adic\u00ed algoritmus \u2013 tch\u00e8que<\/a><\/li><\/ol><\/div>\n<div class=\"feature-video\">\n <h2>\n  \u30bd\u30fc\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac\u30fb\u95a2\u9023\u52d5\u753b\n <\/h2>\n <div class=\"video-item\">\n  \n  <figure class=\"wp-block-embed is-type-video is-provider-youtube wp-block-embed-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\">\n   <div class=\"wp-block-embed__wrapper\">\n    <iframe loading=\"lazy\" title=\"\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3010\u30bd\u30fc\u30c8\u306e\u52d5\u304d\u2460\u3011\u30d0\u30d6\u30eb\u30bd\u30fc\u30c8,\u9078\u629e\u30bd\u30fc\u30c8,\u633f\u5165\u30bd\u30fc\u30c8\uff0f\u57fa\u672c\u60c5\u5831\u6280\u8853\u8005\u30fb\u9ad8\u6821\u60c5\u5831\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/R9LkFlZz4Bc?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n   <\/div>\n  <\/figure>\n  \n <\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u5c0e\u5165 \u30bd\u30fc\u30c8 \u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf \u30b5\u30a4\u30a8\u30f3\u30b9\u307e\u305f\u306f\u6570\u5b66\u306b\u304a\u3044\u3066\u3001\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306e\u30b3\u30ec\u30af\u30b7\u30e7\u30f3\u3092\u7279\u5b9a\u306e\u9806\u5e8f\u3067\u6574\u7406\u3067\u304d\u308b\u3088\u3046\u306b\u3059\u308b\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u4e26\u3079\u66ff\u3048\u3089\u308c\u308b\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306f\u3001\u9806\u5e8f\u95a2\u4fc2 (\u901a\u5e38\u306f\u5168\u4f53\u306e\u9806 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":20131,"comment_status":"","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"https:\/\/img.youtube.com\/vi\/qSAKENP-r48\/0.jpg","fifu_image_alt":"\u30bd\u30fc\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306b\u3064\u3044\u3066\u8a73\u3057\u304f\u89e3\u8aac","footnotes":""},"categories":[5],"tags":[909,21880,11,13,10,14,1091,12,8,16,15,9],"class_list":["post-20130","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-dictionary","tag-algorithme","tag-algorithme-de-tri","tag-techniques","tag-technologie","tag-actualite","tag-news","tag-tri","tag-dossier","tag-definition","tag-sciences","tag-article","tag-explications"],"_links":{"self":[{"href":"https:\/\/science-hub.click\/index.php?rest_route=\/wp\/v2\/posts\/20130"}],"collection":[{"href":"https:\/\/science-hub.click\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/science-hub.click\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/science-hub.click\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/science-hub.click\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=20130"}],"version-history":[{"count":0,"href":"https:\/\/science-hub.click\/index.php?rest_route=\/wp\/v2\/posts\/20130\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/science-hub.click\/index.php?rest_route=\/wp\/v2\/media\/20131"}],"wp:attachment":[{"href":"https:\/\/science-hub.click\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=20130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/science-hub.click\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=20130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/science-hub.click\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=20130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}