問題タブ [proof]

比較ベースの並べ替えは nlog(n) の大きなオメガであるため、mergesort をO(n)にすることはできません。それにもかかわらず、次の証明で問題を見つけることができません。

命題P(n) : 長さnのリストの場合、mergesort はO(n)時間かかります。

P(0) : 空のリストのマージ ソートは空のリストを返します。

強い帰納法: P(1), ..., P(n-1)を仮定し、 P(n )を証明しようとします。再帰的なマージソートの各ステップで、2 つのほぼ「半分のリ​​スト」がマージソートされてから「圧縮」されることがわかっています。各ハーフリストのマージソートには、帰納法によりO(n/2) 時間かかります。圧縮にはO(n)時間がかかります。したがって、アルゴリズムには、M(n) = 2M(n/2) + O(n)の再帰関係があり、これは2O(n/2) + O(n)であり、O(n)です。

私は自分のテストでこの質問を間違え、誰かがそれを説明できるかどうか疑問に思っていました。そして、結論に達するためにとられたステップを示しました。どんな助けでもいただければ幸いです。

L_neq = {0 ^ i1 ^j|のPL証明で i <j} m状態のDFAが与えられた場合、誰かが文字列0 ^（m / 2）1 ^（m / 2 + 1）を選択します。次に、y = 0を選択し、ポンピングすることで、L_neqの外側にある文字列0 ^（m / 2 + 1）1 ^（m / 2 + 1）に到達できることを示します。この証明は正しいですか？なぜまたはなぜそうではないのですか？

さらに、この証明が間違っている場合は、正しい証明を書き留めてください。

ありがとう

CLRSアルゴリズムの本からこの演習のヒントが必要です。

高さhの二分探索木でどのノードから開始しても、Tree-Successorへのk回の連続呼び出しにはO（k + h）時間がかかることを証明します。

big-O 表記法ではO((log n)^k) = O(log n)、 is はどこkにあるのでしょうか (たとえば、ループの対数の数)、真ですか?

私は教授から、この声明は真実であると言われましたが、コースの後半で証明されると彼は言いました。誰かがその有効性を実証できるか、それが真実かどうかを確認できるリンクを持っているかどうか疑問に思っていました.

a> b> 0、b ^ nがO（a ^ n）、n> = 1であるような実数a、bについて証明します。

私は離散数学で所有しているいくつかの教科書を検索しました。また、この証明に関連する類似の例や定理をオンラインで検索しました。私は直接的な解決策を探していませんが、おそらく証明を解決するための正しい方法やパラダイムが示されています。

誰かが次の問題の解決策の数学的部分を教えてくれませんか。

実行時間がnの少なくとも半分で線形である比較ソートがないことを示してください！長さnの入力。長さnの入力の1/nの一部はどうですか？分数（1 /（2）^ n）はどうですか？

解決：

ソートがm個の入力順列に対して線形時間で実行される場合、m個の対応する葉とその祖先で構成される決定木の部分の高さhは線形です。定理8.1の証明と同じ引数を使用して、m = n！/ 2、n！/ n、またはn！/2nではこれが不可能であることを示します。2 ^h≥mであるため、h≥lgmになります。ここに示されているすべての可能なmsについて、lgm =Ω（nlg n）、したがってh =Ω（nlg n）です。特に、

私は自分自身の些細な小さな関数 (便宜上 php) を書きましたが、誰かがその帰納法によって証明を構築するのを手伝ってくれることを望んでいました。

その結果、a[0] が 0 に初期化されたため、各インデックスの値はインデックス自体と同じになります。

目標は、不変式 (それ自体が疑わしいかもしれませんが、うまくいけば要点がわかる) が k+1 に対して成立することを証明することです (または証明する必要があります)。

ありがとう

編集: 例: http://homepages.ius.edu/rwisman/C455/html/notes/Chapter2/LoopInvariantProof.htm

この加重乱数ジェネレーターを使用しました。

次のように：

結果に 、 、7が8よく見られます。910

これが確率論に対して正しいという証拠または保証はありますか?

(log n)^k = O(n)? For k greater or equal to 1.

私の教授はクラスでこのステートメントを提示しましたが、関数がO（n）の時間計算量を持つことの意味がわかりません。のようなものでさえn^2 = O(n^2)、関数f（x）はどのようにして実行時の複雑さを持つことができますか？

ステートメントに関しては、O（（logn）^ k）ではなくO（n）とどのように等しいのでしょうか。