{"version":"1.0","categories":[],"blog_title":"\u30d6\u30ed\u30b0\u540d","title":"FPS \u9006\u5143\u8a08\u7b97\u306e 5/6 \u500d\u9ad8\u901f\u5316 \u2014\u2014 \u3081\u3056\u305b 10 \u2131\u2099 (n \u306f 2 \u51aa)","author_url":"https://blog.hatena.ne.jp/ngtkana/","provider_name":"Hatena Blog","height":"190","description":"\u524d\u56de: \u5f62\u5f0f\u7684\u51aa\u7d1a\u6570\u306e\u30cb\u30e5\u30fc\u30c8\u30f3\u6cd5 (2\u6b21\u53ce\u675f\u6027\u306e\u8a3c\u660e) - \u30d6\u30ed\u30b0\u540d \u5c0e\u5165 \u30cb\u30e5\u30fc\u30c8\u30f3\u6cd5\u306e\u30dc\u30c8\u30eb\u30cd\u30c3\u30af\u306f FFT / IFFT \u3067\u3059\u3002\u9577\u3055 $n$ \u306e\u914d\u5217\u3092 FFT or IFFT \u3059\u308b\u8a08\u7b97\u91cf\u3092 $\\mathcal{F} _ n$ \u3068\u3059\u308b\u3068\u3001\u30cb\u30e5\u30fc\u30c8\u30f3\u6cd5\u306e\u8a08\u7b97\u91cf\u306f $k \\cdot \\mathcal{F} _ n + O(n)$ \u3068\u66f8\u3051\u307e\u3059\u3002\u9762\u5012\u3067\u3059\u304b\u3089\u3053\u308c\u4ee5\u964d\u3053\u306e $O(n)$ \u306f\u7701\u7565\u3057\u3001$k$ \u3092\u5c0f\u3055\u304f\u3059\u308b\u3053\u3068\u3092\u76ee\u6307\u3057\u307e\u3057\u3087\u3046\u3002\u307e\u305f\u3001$n$ \u306f $2$ \u51aa\u3067\u3042\u308b\u3053\u3068\u3092\u4eee\u5b9a\u3057\u307e\u3059\u3002\u4e00\u822c\u306e\u5834\u5408\u306f $2$ \u51aa\u62e1\u5f35\u3092\u884c\u3046\u306e\u3067\u3001\u3053\u306e $k$ \u306e\u5024\u304c $2$ \u500d\u306b\u306a\u308b\u3053\u3068\u306b\u6ce8\u610f\u3067\u3059\u3002 \u30cb\u30e5\u30fc\u30c8\u30f3\u6cd5\u306e\u2026","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.ngtkana.com%2Fentry%2F2026%2F07%2F24%2F031619\" title=\"FPS \u9006\u5143\u8a08\u7b97\u306e 5/6 \u500d\u9ad8\u901f\u5316 \u2014\u2014 \u3081\u3056\u305b 10 \u2131\u2099 (n \u306f 2 \u51aa) - \u30d6\u30ed\u30b0\u540d\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","blog_url":"https://blog.ngtkana.com/","image_url":null,"author_name":"ngtkana","width":"100%","provider_url":"https://hatena.blog","url":"https://blog.ngtkana.com/entry/2026/07/24/031619","type":"rich","published":"2026-07-24 03:16:19"}