やりたいこと
O(N/k)の計算をk=1からk=Nまで計算するときの計算量を計算したいです。
(O(オー)はオーダー記法です。)
そのために下記のように求めようとしているがわからず困っている
計算量を計算するために大体のオーダーを求めると下記等式が成立するようです。
これは、どうやって計算すればよいのでしょうか。
ちょっとぐぐってみたら、
と等式は無限級数和から求めることができたのですが、
というのは計算方法がわからず困っています。
よろしくおねがいします。
O(N/k)の計算をk=1からk=Nまで計算するときの計算量を計算したいです。
(O(オー)はオーダー記法です。)
計算量を計算するために大体のオーダーを求めると下記等式が成立するようです。
これは、どうやって計算すればよいのでしょうか。
ちょっとぐぐってみたら、
と等式は無限級数和から求めることができたのですが、
というのは計算方法がわからず困っています。
よろしくおねがいします。
設問者が提示している級数(の部分和)には名前がついていて調和級数(の部分和)と呼びます。
概略的には積分∫[k=1,N+1]1/kdk = log(N+1) ⋍ logNであること及び級数の部分和がこの積分として近似しうることからオーダーはlogNであると私は理解しています。
より緻密な計算については、以下を参考にされたほうがよろしいと思います。