O（LogN）== O（3LogN）ですか？

私はちょうどAsymptotic Analysisのコースを開始しました。私たちの課題の1つでは、複雑さを変えずに関数に関数を追加することになっています。複雑さはlog（N）です。宿題の指針は、ランタイムを「一定」で変更するよう具体的に求めています。 3Log（N）を定数で変更すると考えられるでしょうか？O（LogN）== O（3LogN）ですか？

出典

2012-04-27 devjeetroy

あなたは 'O（log N）'の正確な定義を忘れましたか？その答えが自明であることを理解するための定義に戻る* yes * –

'3log（n）'の取得方法は？ – noMAD

私は、（定数+ log（N））のような何かを加えることは定数を加えると考えられますが、3LogNは乗算されると考えています。私はO（3LogN）= o（LogN）という定義を知っていますが、インストラクターが添加剤の形を意味すると感じています。私は私の任務で何らかのチャンスを取ることを望んでいなかったので、もっと知識のある人と明確にしたいと思っています。 – devjeetroy

はい、具体的には、これは倍数定数で変更されます。 log(N)+5のような加法定数でそれを変更することもできます。

出典

2012-04-27 05:08:27 trutheality

はい、この問題は、3のような何かのアルゴリズムを変更することは、最適な解決策ではないかもしれないネストされたループを3回だけ実行するようなことがない限り、起こりそうもありません。 – noMAD

元の関数は、バイナリ検索ツリーに要素を追加することでした。私の割り当てを完了するには、一度ではなく2回、ツリーを横切るようにコードを修正しなければなりませんでした。それは2LogNですか？ – devjeetroy

@noMADデータ構造を定数で渡す必要があることは珍しくありません。また、繰り返し内に一定数の操作を追加することも珍しくありません。 – trutheality

O（LogN）== O（3LogN）ですか？

答えて

関連する問題