3

やりたいこと

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

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

計算量を計算するために大体のオーダーを求めると下記等式が成立するようです。
Σ_{k=1~N} (N/k) = NlogN

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

ちょっとぐぐってみたら、
Σ_{k=1~∞} (1/k) = ∞
と等式は無限級数和から求めることができたのですが、
Σ_{k=1~N} (1/k) = logN
というのは計算方法がわからず困っています。

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

3
  • 参考として: detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1020155760
    – masm
    Commented 2018年9月16日 5:45
  • この質問におけるO(オー)は何を意味していますか?アルゴリズムの分野ではいわゆるオーダ記法を指すことが多いと思いますが、質問を読むと単にO(x)=xなどと捉えることもできます。また質問自体も1つ目の等式が成立する理由を訪ねているだけで、計算量は関係ないようにも思われます。等式と計算量との関係などについて情報を追記していただけないでしょうか?
    – letrec
    Commented 2018年9月16日 7:24
  • ありがとうございます、情報を追記しました。 Commented 2018年9月16日 8:41

1 件の回答 1

2

設問者が提示している級数(の部分和)には名前がついていて調和級数(の部分和)と呼びます。
概略的には積分∫[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

1
  • 参考:数学において級数とは無限項に連なる数列に対する総和(つまりN=∞)を級数と呼びますので、少し煩雑な記述ですが(の部分和)という表記を足しています。 Commented 2018年9月16日 10:00

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。