このような反復関係にはどのようにしっかりとした境界がありますか?これはhw問題であり、m/log(m)が厳密な漸近線であることを証明することが期待されます。私は誘導を使ってみましたが、どこにも行かないようです。対数ルールで何かが欠けているか、それ以上のことがあります。反復T(n)= T(n - log(n))+ 1
0
A
答えて
1
誘導。すべてk < n
の場合はC
の場合はT(k) <= C k/log k
とします。
アンロール再発(n/2)/log(n/2)
回、(私たちはT(n)
とlog(n)
両方が単調関数であるという事実を利用)log(n/2)
でlog(.)
を交換します。それは今、あなたは右の式はC n/log n
で囲まれていることを証明する必要があり、
T(n) <= T(n - log(n/2) * (n/2)/log(n/2)) + (n/2)/log(n/2)
T(n) <= T(n/2) + (n/2)/log(n/2)
T(n) <= C (n/2)/log(n/2) + (n/2)/log(n/2)
です。 Arthmeticsとそのような発見はC
です。
関連する問題
- 1. 反復法によるT(n)= T(n-1)+(n-1)の解き方は?
- 2. T(N)= T(N/2)+ T(N/4)は、漸化式</p> <p>T(N)= T(N/2)+ Tを解決するためにどのように反復法
- 3. もしT(n)=θ(n^2)がT(n)= 0(n)ならば?
- 4. A(n)= A(n-1)+ n * log(n)?
- 5. /n/t/t myValue \ n \ t \ tなしでxmlファイルから読み取る方法
- 6. タイプT [N]のオブジェクトにT(&ref)[N]をバインドします。
- 7. T(n)= 2T(n/2)+ O(n)からO(nlogn)を得る方法
- 8. std :: type T **とT * [N]の検索
- 9. log(n!)= O((log(n))^ 2)ですか?
- 10. O(1)、O(n log n)、O(log n)の複雑さを持つアルゴリズムの例
- 11. T-SQLの更新1の参加:N
- 12. CHOICE/c wasd/n/t 0.5
- 13. バイナリ検索はO(log n)かO(n log n)ですか?
- 14. 1/N + 2/N-1 + 3/N-2 + ... N/1
- 15. 私はHashMapを変換しますか[T、フューチャー[N]]フューチャー[HashMapの[T、N]]
- 16. エスケープ\ nを\ T \ T JSON出力の新しい\ nを削除する方法
- 17. マスター定理、再発を解決する、T(N)= 3T(N/2)+ nlogn
- 18. \ r \ n、\ n、\ tを "\"と置き換えるGroovyスクリプト
- 19. ログ(O(n * log(n)))は何ですか?
- 20. n個の値の反復
- 21. n^2 + T(n-1)に対して、この単純なアルゴリズムT(n/2)+1の最悪の場合の時間の複雑さはなぜですか?
- 22. A [n-1]> = A [n] <= A [n + 1]
- 23. \ tと\ nの束を返すAPI
- 24. 治療中のストリップ\ n \ t \ r
- 25. Javaペア<T,N>クラス実装
- 26. Matlabスクリプトa(n)= a(n-1)+ a(n-2)
- 27. 複雑さ(N *(N-1)/ 2)
- 28. O(n^2 * log(n))とO(n^3)どちらが大きいですか?
- 29. なぜn log(n)がnより優位を占めるのか?
- 30. f(n)= log(n)^ mはすべての自然数mに対してO(n)
誘導を開始する方法を教えてください。誰かがあなたを助けてくれるかもしれません。 – ShadowMitia