問題タブ [big-theta]

次の解決策が正しいかどうか誰か教えてもらえますか?

t(n) = t(n-2) + (n-2)²の実行時間を計算しようとしています

さらに評価する

=> t(n)=t(n-4) + (n-2)² + n²

=> t(n)=t(n-6) + (n-6)² + (n-2)² + n²

...これは 2 だけ減っているので、約 n/2 項になり、すべての正方形を展開すると (n/2) * (n²) となり、これは n³ に等しくなります。したがって、実行時間はtheta(n³)です。

これは正しい解決策ですか？

このアルゴリズム (疑似コード) を分析すると、完了するまでに必要なステップ数を数えることができ、線形アルゴリズムであるシータ表記 Θ(n) でその効率を分析できます。わかった。

次のコードは、終了するためにループ内の内部式に依存しています。

明らかに最初のものほど単純ではなく、ループ内の A と B のインクリメントが不規則であるため、ループが 100 回繰り返されるとは言えません。効率を調べるために、この特定のアルゴリズムのステップ数をカウントするにはどうすればよいですか?

前にこの質問を説明した方法でエラーを見つけたので、ここでもう一度説明します。

このアルゴリズム (疑似コード) を分析すると、完了するまでに必要なステップ数を数えることができ、線形アルゴリズムであるシータ表記 Θ(n) でその効率を分析できます。わかった。

この次のコードは、終了するためにループ内の内部式に依存します。コードには変数 N がないため、値 1 を代入しているため、このアルゴリズムの効率は常に同じになります。 A 変数と B 変数の両方:

今では、このアルゴリズムは常に一定の時間で実行されると信じています。しかし、完了するまでに必要なステップ数を知るために代数を使用するにはどうすればよいでしょうか?

私は本から漸近記法を研究していますが、著者が何を意味するのか理解できません。私はそれを知っていif f(n) = Θ(n^2) then f(n) = O(n^2)ます。しかし、著者の言葉から、挿入ソート関数のアルゴリズムf(n) = Θ(n)とf(n)=O(n^2)。

なんで？ビッグオメガまたはビッグシータは、入力が異なると変化しますか？

彼はこう言った：

「しかし、挿入ソートの最悪の場合の実行時間に制限されたΘ（n ^ 2）は、すべての入力の挿入ソートの実行時間に制限されたΘ（n ^ 2）を意味するものではありません。」

ただし、ビッグオー表記では異なります。彼はどういう意味ですか？それらの違いは何ですか？

私は困惑している。以下にコピーして貼り付けています。

O表記は上限を表すため、これを使用してアルゴリズムの最悪の場合の実行時間を制限すると、すべての入力でアルゴリズムの実行時間に制限があります。したがって、挿入ソートの最悪の場合の実行時間に制限されたO（n ^ 2）は、すべての入力の実行時間にも適用されます。ただし、挿入ソートの最悪の場合の実行時間に制限されたΘ（n ^ 2）は、すべての入力の挿入ソートの実行時間に制限されたΘ（n ^ 2）を意味するものではありません。たとえば、入力がすでにソートされている場合、挿入ソートはΘ（n）時間で実行されます。

私は試験でこの問題を間違えました: O(n)でもOmega(n)でもない関数を挙げてください。

YouTube を通じて自分でこのことを学ぼうとした後、これが正しい答えかもしれないと考えています。

(n ³ (1 + sin n)) は O(n) でも Omega(n) でもありません。

それは正確でしょうか？

誰かがこの質問を理解するのを手伝ってくれますか? 明日の試験でそれがあるかもしれませんが、インターネットや講義で同様の問題を見つけることができません.

これは、数独 (9x9) を解くためのコードです。

このアルゴリズムを Big O または Big Theta 表記で分類するのを手伝ってくれる人がいますか? 私は O(n^3) を取得しましたが、ご覧のとおり、そうではありません! それで、どうやって始めるかのヒントやアドバイスをください。とても感謝しています。必要に応じて、これを疑似コードで投稿することもできます。

ありがとう、MB

宿題でビッグ シータを計算するように頼まれましたが、この分野に関する講義資料は少し少なめでした。

与えられたループ

私は実行チャートを次のように作成しました

私を悩ませているのは、内側のループインクリメンターです。これは (n+1)/2 回実行されるため、ビッグ シータは (n log n + log n)/2 である必要があります。

私は正しいですか？

ブロックは次のとおりです。

x=x+1 が実行される回数のシータ表記を見つける必要があります。いくつかのサンプル値を含むテーブルを作成しましたが、そこから先に進む方法がわかりません。ここに私のサンプル値があります:

この関数の Big-Theta の実行時間を把握するのに少し助けが必要です。

for ループが関数内にない場合、この関数の実行時間がどのようになるかはわかっていますが、ループが原因で少し気分が落ち込んでいます。何かアドバイス？