9

これは厳密にはプログラミングの質問ではないことはわかっていますが、コンピューター サイエンスの質問であるため、誰かが私を助けてくれることを願っています。

私はアルゴリズムの宿題に取り組んでおり、いくつかのアルゴリズムの Big-Oh、Big-Omega、Theta などを考え出しています。私はそれらの C 値と N 0値を見つけることによってそれらを証明していますが、すべてうまくいっています。

しかし、私はセットの最後の 2 つの問題に遭遇し、その方法を理解するのに苦労しています (そして、Google はあまり役に立ちません)。

これまで、合計の Big-Oh/Omega を理解する必要はありませんでした。

私の最後の2つの問題は次のとおりです。

  • i 2のΣ(i=1～n)がO(N 3 ) であることを示せ

と

  • [log 2 i]のΣ(i=1～n)がΩ(n log n)であることを示せ

私の質問は、どうすればそれを示すことができますか?

たとえば、最初のものでは、直感的に、i 2の合計が O(N 3 ) であることがわかりません。2番目のものは私をさらに混乱させます。誰かがこれらの合計の Big-Oh と Big-Omega を表示する方法を説明できますか?

4

5 に答える 5

1

http://en.wikipedia.org/wiki/Big_O_notation

g(m)=O(f(m)) の N 回の繰り返しはO(N*f(m))、任意の f(N) に対してです。

i*g(i) の i=1..N の合計はO(N*f(N))、g(n)=O(f(n)) で f が単調な場合です。

定義: g(n)=O(f(n)) c,m が存在する場合、すべての n>m に対して、g(n)<=c*f(n)

合計は i=1..N ofi*f(i)です。

f が i において単調である場合、これはすべての項が <= i f(N) <= N f(N) であることを意味します。したがって、合計はより小さいN*c*f(N)ので、合計はO(N*f(N))(g(n)=O(f(n)) を作る同じ c,m によって目撃される)

もちろん、log_2(x) と x^2 はどちらも単調です。

于 2009-09-04T05:01:05.857 に答える
1

私の推測では、質問文が意味するのは、最初のケースでは実行時間が i 2に比例し、2 番目のケースでは log 2 i に比例する計算の結果を合計している場合です。どちらの場合も、全体的な合計の実行時間は、合計内の N のより大きな値によって「支配」されるため、両方の全体的な big-O 評価は N*O(f) になります。ここで、f は関数です。再集計。

于 2009-09-04T05:06:08.077 に答える
1

私が思いつく最も簡単なアプローチは、帰納法による証明です。

最初のものについては、本質的にそれを示す必要があります

sum (i=1 to n) i^2 < k*n^3, k > 2,n > 0

誘導の一般化された原理を使用し、n=1 および k=2 の基本ケースを取るとします。

私たちは得る1<2*1。

もちろん、帰納的仮説を取ると、次のことがわかります。

sum(i=1 to n) i^2<k *n^3、ちょっとした楽しい数学で、

sum(i=1 to n) i^2+(n+1)^2 < k *n^3+(n+1)^2.

  • 今すぐ表示k * n^3+(n+1)^2 < k *(n+1)^3

  • k *n^3+n^2+2n+1 < k *n^3+k *(3n^2+3n+1)

  • k *n^3 < k *n^3+(3k-1) *n^2+(3k-2) *n+k-1

したがって、元の結果は正しいです。

2 番目の証明では、それを示す必要がありますが sum(i=1 to n) log_2(i) >= k*n*log(n)、これは読者の演習として残しておきます ;)。

ただし、主なステップは ですsum(i=1 to n) log_2(i)+log_2(n+1)>=k*n*log(n)+k*log(n+1)。ある k については、明らかに k は 1 です。

于 2009-09-04T05:15:16.780 に答える
0

おそらく、CPU は一定時間で 32 ビット整数を乗算します。しかし、big-Oh は「40 億未満」を気にしないので、掛け算のアルゴリズムを調べる必要があるのではないでしょうか?

Wolframによると、「従来の」乗算アルゴリズムは O(n 2 ) です。この場合のnは桁数であるため、実際にはlog(n)が実際の数になります。したがって、整数 1..n を時間 O(n.log(n)) で 2 乗できるはずです。合計は O(log(n 2 )) であり、これは明らかに O(log(n)) であり、全体の複雑度は O(n.log(n)) です。

ですから、あなたの混乱はよく理解できます。

于 2009-09-04T05:14:43.707 に答える