{"image_url":null,"blog_title":"\u3048\u3073\u3061\u3083\u3093\u306e\u65e5\u8a18","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2Frsk0315.hatenablog.com%2Fentry%2F2021%2F05%2F18%2F015511\" title=\"\u7720\u308c\u306a\u3044\u591c\u306f\u7d20\u6570\u306e\u500b\u6570\u3067\u3082\u6570\u3048\u307e\u3057\u3087\u3046 - \u3048\u3073\u3061\u3083\u3093\u306e\u65e5\u8a18\" class=\"embed-card embed-blogcard\" scrolling=\"no\" frameborder=\"0\" style=\"display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;\"></iframe>","height":"190","provider_url":"https://hatena.blog","url":"https://rsk0315.hatenablog.com/entry/2021/05/18/015511","author_name":"rsk0315","description":"\u5225\u306b\u3001\u304a\u3075\u3068\u3093\u304b\u3089\u51fa\u305f\u304f\u306a\u3044\u671d\u3068\u304b\u306b\u6570\u3048\u3066\u3082\u3044\u3044\u3068\u601d\u3044\u307e\u3059\u3002 \\(n\\) \u4ee5\u4e0b\u306e\u7d20\u6570\u306e\u500b\u6570\u3092\u6570\u3048\u305f\u3044\u3068\u304d\u3069\u3046\u3057\u307e\u3059\u304b\uff1f \u5404\u6574\u6570 \\(2\\le i\\le n\\) \u306b\u5bfe\u3057\u3066\u7d20\u6570\u5224\u5b9a\u3057\u3066\u6570\u3048\u307e\u3059\uff1f \u7d20\u6570\u5224\u5b9a\u3092\u8a66\u3057\u5272\u308a\u6cd5\u3067\u3084\u308b\u3068 \\(\\Theta(n\\sqrt{n})\\)\u3001\u7dda\u5f62\u7be9*1\u3092\u4f7f\u3048\u3070 \\(\\Theta(n)\\) \u3068\u304b\u3067\u3059\u306d\u3002 \u3053\u308c\u3092 \\(o(n)\\) \u3067\u3067\u304d\u305f\u3089\u3046\u308c\u3057\u304f\u306a\u3044\u3067\u3059\u304b\uff1f\u3068\u3044\u3046\u8a71\u3067\u3059\u3002 \u4eca\u56de\u306f \\(O(\\sqrt{n})\\) space, \\(O(n^{3/4}/\\log(n))\\) time \u306e\u8a71\u304c\u30e1\u30a4\u30f3\u3067\u3059\u3002 \u5b9a\u6570\u500d\u304c\u3042\u307e\u308a\u8efd\u304f\u306a\u3044 \\(O(n^{2/3})\\) space, \\\u2026","categories":[],"provider_name":"Hatena Blog","published":"2021-05-18 01:55:11","version":"1.0","author_url":"https://blog.hatena.ne.jp/rsk0315/","width":"100%","type":"rich","blog_url":"https://rsk0315.hatenablog.com/","title":"\u7720\u308c\u306a\u3044\u591c\u306f\u7d20\u6570\u306e\u500b\u6570\u3067\u3082\u6570\u3048\u307e\u3057\u3087\u3046"}