

### やりたいこと

O(N/k)の計算をk=1からk=Nまで計算するときの計算量を計算したいです。  
（O(オー)はオーダー記法です。）

### そのために下記のように求めようとしているがわからず困っている

計算量を計算するために大体のオーダーを求めると下記等式が成立するようです。  
![Σ_{k=1~N} \(N/k\) =
NlogN](https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bk=1%7D%5E%7BN%7D%5Cfrac%7BN%7D%7Bk%7D%20=%20N%20%5Clog%20N)

これは、どうやって計算すればよいのでしょうか。

ちょっとぐぐってみたら、  
![Σ_{k=1~∞} \(1/k\) =
∞](https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bk=1%7D%5E%7B%5Cinfty%7D%5Cfrac%7B1%7D%7Bk%7D%20=%5Cinfty)  
と等式は無限級数和から求めることができたのですが、  
![Σ_{k=1~N} \(1/k\) =
logN](https://chart.googleapis.com/chart?cht=tx&chl=%5Csum_%7Bk=1%7D%5E%7BN%7D%5Cfrac%7B1%7D%7Bk%7D%20=%5Clog%20N)  
というのは計算方法がわからず困っています。

よろしくおねがいします。


CC BY-SA 4.0
2018-09-16T04:56:02.313
48445
2018-09-16T09:59:30.000
2018-09-16T08:41:31.973
23717
23717
question
c アルゴリズム 数学
O(N/k)をk=1からk=Nまで計算したときの計算量


設問者が提示している級数(の部分和)には名前がついていて調和級数(の部分和)と呼びます。  
概略的には積分∫[k=1,N+1]1/kdk = log(N+1) ⋍
logNであること及び級数の部分和がこの積分として近似しうることからオーダーはlogNであると私は理解しています。

より緻密な計算については、以下を参考にされたほうがよろしいと思います。

<https://ja.wikipedia.org/wiki/%E8%AA%BF%E5%92%8C%E7%B4%9A%E6%95%B0#%E7%A9%8D%E5%88%86%E5%88%A4%E5%AE%9A%E6%B3%95>

<https://ameblo.jp/mossalmon/entry-12320091570.html>


CC BY-SA 4.0
2018-09-16T09:52:22.510
48454
2018-09-16T09:59:30.000
2018-09-16T09:59:30.000
25980
25980
48445
answer