[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/9#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/9","headline":"Barnes-Hut-Algorithmus  –  Wikipedia","name":"Barnes-Hut-Algorithmus  –  Wikipedia","description":"before-content-x4 Barnes-Hat\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 1986\u5e74\u306bJosh Barnes\u3068Piet Hut\u306b\u3088\u3063\u3066\u516c\u958b\u3055\u308c\u305f\u8fd1\u4f3c\u624b\u9806\u3067\u3042\u308a\u3001\u3053\u308c\u306b\u3088\u308a\u3001N\u30dc\u30c7\u30a3\u306e\u554f\u984c\u306b\u304a\u3051\u308b\u529b\u306e\u52b9\u679c\u7684\u306a\u8a08\u7b97\u304c\u53ef\u80fd\u3067\u3059\u3002\u90e8\u968a\u306e\u76f4\u63a5\u306e\u9762\u7a4d\u3068\u306f\u5bfe\u7167\u7684\u306b\u3001\u5f7c\u3089\u306e\u30b3\u30f3\u30d4\u30e5\u30fc\u30c6\u30a3\u30f3\u30b0\u8cbb\u7528 o \uff08 n 2\uff09\uff09 {displaystyle o\uff08n^{2}\uff09} after-content-x4 \u4e0a\u6607\u3001\u30d0\u30fc\u30f3\u30ba\u30cf\u30c3\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u52aa\u529b\u304c\u524a\u6e1b\u3055\u308c\u307e\u3057\u305f o \uff08 n \u30ed\u30b0 \u2061 n \uff09\uff09","datePublished":"2023-01-01","dateModified":"2023-01-01","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/author\/lordneo#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/author\/lordneo","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e5d43a3df904fa4d7220f5b86285298aa36d969b","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/e5d43a3df904fa4d7220f5b86285298aa36d969b","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/9","wordCount":1850,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4 Barnes-Hat\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 1986\u5e74\u306bJosh Barnes\u3068Piet Hut\u306b\u3088\u3063\u3066\u516c\u958b\u3055\u308c\u305f\u8fd1\u4f3c\u624b\u9806\u3067\u3042\u308a\u3001\u3053\u308c\u306b\u3088\u308a\u3001N\u30dc\u30c7\u30a3\u306e\u554f\u984c\u306b\u304a\u3051\u308b\u529b\u306e\u52b9\u679c\u7684\u306a\u8a08\u7b97\u304c\u53ef\u80fd\u3067\u3059\u3002\u90e8\u968a\u306e\u76f4\u63a5\u306e\u9762\u7a4d\u3068\u306f\u5bfe\u7167\u7684\u306b\u3001\u5f7c\u3089\u306e\u30b3\u30f3\u30d4\u30e5\u30fc\u30c6\u30a3\u30f3\u30b0\u8cbb\u7528 o \uff08 n 2\uff09\uff09 {displaystyle o\uff08n^{2}\uff09}        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4\u4e0a\u6607\u3001\u30d0\u30fc\u30f3\u30ba\u30cf\u30c3\u30c8\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u52aa\u529b\u304c\u524a\u6e1b\u3055\u308c\u307e\u3057\u305f o \uff08 n \u30ed\u30b0 \u2061 n \uff09\uff09 {displaystyle o\uff08nlog n\uff09} \u3002 n\u4f53\u306e\u554f\u984c\u306e\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u306f\u3001\u5929\u6587\u5b66\u306e\u6a19\u6e96\u7684\u306a\u30bf\u30b9\u30af\u3067\u3059\u3002\u3053\u306e\u3088\u3046\u306a\u554f\u984c\u304c\u3042\u308b\u3068\u3001\u6570\u5b57\u304c\u52d5\u304d\u307e\u3059\uff08 n \uff09\u529b\u306e\u5f71\u97ff\u4e0b\u306b\u3042\u308b\u8eab\u4f53\u306e\u3002\u305d\u308c\u306f\u3001\u4ed6\u306e\u3059\u3079\u3066\u306e\u8eab\u4f53\u306e\u4f4d\u7f6e\u306b\u4f9d\u5b58\u3057\u307e\u3059\u3002\u4f8b\u3068\u3057\u3066\u3001\u9280\u6cb3\u306e\u91cd\u529b\u5834\u3067\u306e\u661f\u306e\u52d5\u304d\u3092\u53c2\u7167\u3057\u307e\u3059\u3002\u76f4\u63a5\u7684\u306a\u7d71\u5408\u306f\u3001\u4f53\u306b\u4f5c\u7528\u3059\u308b\u529b\u304c\u4ed6\u306e\u4f53\u304b\u3089\u5f71\u97ff\u3092\u4e0e\u3048\u308b\u3059\u3079\u3066\u306e\u529b\u306e\u5408\u8a08\u3067\u3042\u308b\u305f\u3081\u3001\u4f53\u306e\u6570\u304c\u5897\u3048\u3066\u975e\u5e38\u306b\u6642\u9593\u3092\u8cbb\u3084\u3057\u3066\u3044\u307e\u3059\u3002\u3057\u305f\u304c\u3063\u3066\u3001\u76f4\u63a5\u4e0d\u8010\u6027\u306b\u57fa\u3065\u304f\u8a08\u7b97\u306f\u3001\u4f53\u306e\u6570\u304c\u5897\u3048\u308b\u3068\u5897\u52a0\u3057\u3066\u3044\u307e\u3059\uff08 n > 10000\uff09\u5f37\u5ea6\u8a08\u7b97\u306e\u7dcf\u6570\u306f\u6b21\u306e\u3068\u304a\u308a\u3067\u3059\u3002        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x412n \uff08 n  –  \u521d\u3081 \uff09\uff09 \u2248 o \uff08 N2\uff09\uff09 {displaystyle {frac {1} {2}} n\uff08n-1\uff09ampto\uff08n^{2}\uff09} \u3053\u306e\u50be\u5411\u306f\u3001\u9ad8\u5ea6\u306b\u4e26\u5217\u5316\u3055\u308c\u305f\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc\u30cf\u30fc\u30c9\u30a6\u30a7\u30a2\uff08GPU\uff09\u3092\u4f7f\u7528\u3059\u308b\u3053\u3068\u3067\u6253\u3061\u6d88\u3059\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u304c\u3001\u554f\u984c\u306f\u3088\u308a\u591a\u304f\u306e\u7c92\u5b50\u306b\u306e\u307f\u79fb\u884c\u3057\u307e\u3059\u3002\u6570\u767e\u4e07\u307e\u305f\u306f\u6570\u5341\u5104\u306e\u7c92\u5b50\u3092\u542b\u3080\u52b9\u679c\u7684\u306a\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u306b\u306f\u3001\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u304c\u5fc5\u8981\u3067\u3042\u308a\u3001\u305d\u306e\u8a08\u7b97\u8cbb\u7528\u306f\u7c92\u5b50\u306e\u6570\u3068\u3068\u3082\u306b\u5e73\u65b9\u306b\u5897\u52a0\u3057\u307e\u305b\u3093\u3002\u3053\u308c\u3089\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e1\u3064\u306f\u3001Barnes and Hat\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3067\u3059\u3002 2\u3064\u306e\u96a3\u63a5\u3059\u308b\u9280\u6cb3\u3067\u30e2\u30c7\u30eb\u5316\u3055\u308c\u305f\u7c92\u5b50\u5206\u5e03\u3002 \u5b8c\u5168\u306a\u30d0\u30fc\u30f3\u30ba\u306e\u5e3d\u5b50\u3002\u9818\u57df\u306f\u3001\u5404\u7c92\u5b50\u304c\u72ec\u81ea\u306e\u7d30\u80de\u306b\u306a\u308b\u307e\u3067\u518d\u5e30\u7684\u306b\u5206\u5272\u3055\u308c\u307e\u3059\u3002 Barnes Hut Baum\u306e\u30bb\u30eb\u306f\u3001\u5ea7\u6a19\u8d77\u70b9\u306e\u7c92\u5b50\u4e0a\u306e\u529b\u3092\u8a08\u7b97\u3059\u308b\u305f\u3081\u306b\u4f7f\u7528\u3055\u308c\u307e\u3059\u3002  \u30b0\u30e9\u30d5\u30a3\u30c3\u30af\u56f3\u9762 [ \u7de8\u96c6 | \u30bd\u30fc\u30b9\u30c6\u30ad\u30b9\u30c8\u3092\u7de8\u96c6\u3057\u307e\u3059 ] \u591a\u6570\u306e\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u9593\u306e\u529b\u306e\u30da\u30a2\u306e\u8a08\u7b97\u306f\u3001\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u30fc\u30b5\u30a4\u30a8\u30f3\u30b9\u306e\u4e00\u90e8\u3068\u3057\u3066\u7fa4\u8846\u306b\u57fa\u3065\u3044\u305f\u30b0\u30e9\u30d5\u30a3\u30c3\u30af\u30b9\u30c8\u30ea\u30fc\u30e0\u5185\u306e\u554f\u984c\u3067\u3082\u3042\u308a\u307e\u3059\u3002\u30b0\u30e9\u30d5\u306e\u30ce\u30fc\u30c9\u9593\u306e\u30a8\u30c3\u30b8\u306f\u30b9\u30d7\u30ea\u30f3\u30b0\u306e\u30b7\u30b9\u30c6\u30e0\u3068\u3057\u3066\u89e3\u91c8\u3055\u308c\u3001\u30b0\u30e9\u30d5\u306f\u30ec\u30d9\u30eb\u306b\u63cf\u753b\u3055\u308c\u3001\u30b9\u30d7\u30ea\u30f3\u30b0\u529b\u304c\u30ad\u30e3\u30f3\u30bb\u30eb\u3055\u308c\u307e\u3059\u3002 Barnes Hat\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u529b\u306e\u53cd\u5fa9\u8a08\u7b97\u3068\u30ce\u30fc\u30c9\u306e\u518d\u914d\u7f6e\u3092\u53ef\u80fd\u306b\u3057\u307e\u3059\u3002 [\u521d\u3081] Barnes Hut\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u7c92\u5b50\u30b0\u30eb\u30fc\u30d7\u306e\u9069\u5207\u306a\u7d44\u307f\u5408\u308f\u305b\u3092\u64ec\u4f3c\u7c92\u5b50\u306b\u9069\u5207\u306a\u7d44\u307f\u5408\u308f\u305b\u306b\u3059\u308b\u3053\u3068\u306b\u3088\u308a\u3001\u8a08\u7b97\u3055\u308c\u308b\u529b\u306e\u6570\u3092\u6e1b\u3089\u3057\u307e\u3059\u3002\u3053\u3053\u3067\u306e\u57fa\u672c\u7684\u306a\u8003\u3048\u65b9\u306f\u3001\u5358\u4e00\u306e\u7c92\u5b50\u4e0a\u306e\u7c92\u5b50\u30b0\u30eb\u30fc\u30d7\u306b\u3088\u3063\u3066\u884c\u4f7f\u3055\u308c\u308b\u529b\u306f\u3001\u7c92\u5b50\u30b0\u30eb\u30fc\u30d7\u306e\u8cea\u91cf\u7126\u70b9\u306b\u304a\u3051\u308b\u5358\u4e00\u8cea\u91cf\u306e\u52b9\u679c\u306b\u3088\u3063\u3066\u975e\u5e38\u306b\u826f\u597d\u306a\u8fd1\u4f3c\u3067\u8fd1\u4f3c\u3067\u304d\u308b\u3068\u3044\u3046\u3053\u3068\u3067\u3059\u3002\u305f\u3068\u3048\u3070\u3001Andromeda Galaxy\u304c\u592a\u967d\u306e\u4e0a\u3067\u884c\u4f7f\u3059\u308b\u529b\u306f\u3001Andromeda Galaxy\u306e\u4e2d\u5fc3\u306b\u4f4d\u7f6e\u3057\u3001\u305d\u306e\u8cea\u91cf\u304c\u3042\u308b\u30dd\u30a4\u30f3\u30c8\u8cea\u91cf\u3092\u901a\u3057\u3066\u975e\u5e38\u306b\u3088\u304f\u8fd1\u3065\u304f\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002\u305f\u3060\u3057\u3001\u3053\u306e\u8fd1\u4f3c\u306f\u8ddd\u96e2\u304c\u3042\u308b\u5834\u5408\u306b\u306e\u307f\u8a31\u53ef\u3055\u308c\u307e\u3059        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4r {displaystyle r} \u500b\u3005\u306e\u7c92\u5b50\u3068\u30b0\u30eb\u30fc\u30d7\u306e\u76f4\u5f84\u304b\u3089\u306e\u30b0\u30eb\u30fc\u30d7 d {displaystyle d} \u8ddd\u96e2\u306b\u95a2\u9023\u3057\u3066\u5c0f\u3055\u3044\u3067\u3059\u3002\u30b0\u30eb\u30fc\u30d7\u306e\u76f4\u5f84\u3068\u30b0\u30eb\u30fc\u30d7\u9664\u53bb\u306e\u6bd4\u7387\u306f\u3001\u30de\u30eb\u30c1\u30dd\u30fc\u30eb\u53d7\u3051\u5165\u308c\u57fa\u6e96\u3068\u3057\u3066\u3067\u3059\uff08\u82f1\u8a9e\uff1a \u591a\u91cd\u6975\u53d7\u3051\u5165\u308c\u57fa\u6e96 \u3001Mac\uff09\u8aac\u660e\uff1a \u03b8=dr{displaystyletheta = {frac {d} {r}}} \u3042\u306a\u305f\u306e\u5c0f\u3055\u3044 th {displaystyletheta} \u3001\u8fd1\u4f3c\u306e\u65b9\u304c\u826f\u3044\u3002\u8d85\u3048\u305f th {displaystyletheta} \u5927\u304d\u306a\u30a8\u30e9\u30fc\u3092\u56de\u907f\u3059\u308b\u305f\u3081\u306b\u3001\u7279\u5b9a\u306e\u3057\u304d\u3044\u5024\u3092\u4f7f\u7528\u3057\u306a\u3044\u3067\u304f\u3060\u3055\u3044\u3002\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306f\u3001\u30b7\u30df\u30e5\u30ec\u30fc\u30b7\u30e7\u30f3\u9818\u57df\u3092\u8c61\u9650\uff082D\uff09\u307e\u305f\u306f\u30aa\u30af\u30bf\u30f3\u30c8\uff083D\uff09\u306b\u518d\u5e30\u7684\u306b\u5206\u5272\u3059\u308b\u3053\u3068\u306b\u3088\u308a\u3001\u3053\u306e\u539f\u5247\u3092\u5b9f\u88c5\u3057\u307e\u3059\u3002\u7c92\u5b50\u306f\u3001\u7d50\u679c\u306e\u30c4\u30ea\u30fc\u69cb\u9020\u306e\u30ce\u30fc\u30c9\u306b\u4fdd\u5b58\u3055\u308c\u307e\u3059\u3002\u7d50\u3073\u76ee\u306e\u9664\u53bb\u304c\u5358\u4e00\u306e\u7c92\u5b50\u304b\u3089\u5341\u5206\u306b\u5927\u304d\u3044\u5834\u5408\u3001\u5f37\u5ea6\u8a08\u7b97\u306f\u3001\u7c92\u5b50\u9593\u3067\u306f\u306a\u304f\u3001\u500b\u3005\u306e\u7c92\u5b50\u3068\u30ce\u30fc\u30c9\u306e\u4e3b\u306a\u7126\u70b9\u306e\u9593\u3067\u76f4\u63a5\u884c\u308f\u308c\u307e\u3059\u3002 \u5358\u4e00\u306e\u7c92\u5b50\u3078\u306e\u7c92\u5b50\u5206\u5e03\u306b\u3088\u3063\u3066\u5b9f\u8df5\u3055\u308c\u308b\u529b\u306f\u3001\u7c92\u5b50\u30b0\u30eb\u30fc\u30d7\u3092\u500b\u3005\u306e\u7c92\u5b50\u306b\u9664\u53bb\u3059\u308b\u3068\u3001\u30b0\u30eb\u30fc\u30d7\u30b5\u30a4\u30ba\u306b\u95a2\u9023\u3057\u3066\u5927\u304d\u3044\u5834\u5408\u30011\u70b9\u8cea\u91cf\u306b\u3088\u3063\u3066\u653e\u51fa\u3055\u308c\u308b\u96fb\u529b\u306b\u3088\u3063\u3066\u8fd1\u4f3c\u3067\u304d\u307e\u3059\u3002 \u661fA\u306b\u5bfe\u3059\u308b\u661f\u30af\u30e9\u30b9\u30bf\u30fc\u3068\u661fB\u306e\u91cd\u529b\u52b9\u679c\u306f\u3001\u30dd\u30a4\u30f3\u30c8\u8cea\u91cf\u3068\u3057\u3066\u70b9\u8cea\u91cf\u3068\u3057\u3066\u8fd1\u4f3c\u3067\u304d\u307e\u3059\u3002\u3057\u304b\u3057\u3001\u661f\u306e\u5c71\u306e\u4e2d\u3067\u3055\u3048\u3001\u8239\u5c3eb\u306f\u661f\u306e\u5c71\u304b\u3089\u5341\u5206\u96e2\u308c\u3066\u3044\u308b\u305f\u3081\u3001\u8239\u5c3eB\u306e\u661f\u306e\u5c71\u306e\u91cd\u529b\u306b\u8fd1\u3065\u304f\u3053\u3068\u304c\u3067\u304d\u307e\u3059\u3002 \u30b8\u30e7\u30b7\u30e5\u30fb\u30d0\u30fc\u30f3\u30ba\u3001\u30d4\u30a8\u30c8\u30cf\u30c3\u30c8\uff1a \u968e\u5c64o\uff08n log n\uff09\u529b\u8a08\u7b97\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0 \u3002\u306e\uff1a \u81ea\u7136 \u3002 \u30d0\u30f3\u30c9  324 \u3001 \u3044\u3044\u3048\u3002  6096 \u30011986\u5e7412\u6708\u3001 S.  446\u2013449 \u3001doi\uff1a 10.1038\/324446A0 \u3002  \u30c9\u30a4\u30c4\u4eba  \u82f1\u8a9e  \u2191  Yifan Hu\uff1a \u52b9\u7387\u7684\u3067\u9ad8\u54c1\u8cea\u306e\u30d5\u30a9\u30fc\u30b9\u6307\u5411\u30b0\u30e9\u30d5\u56f3 \u3002\u306e\uff1a Mathematica Journal \u3002 \u30d0\u30f3\u30c9  \u5341 \u3001 \u3044\u3044\u3048\u3002  \u521d\u3081 \u30012006\u3001 S.  37\u201371 \uff08 Mathematica- journal.com [PDF; 2020\u5e7412\u67086\u65e5\u306b\u30a2\u30af\u30bb\u30b9]\uff09\u3002         (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2jp\/wiki10\/archives\/9#breadcrumbitem","name":"Barnes-Hut-Algorithmus  –  Wikipedia"}}]}]