すべてのn、O（1）がO（n）よりも速い場合、O（1）上でO（n）を選択しますか？

すべてのn、O（1）がO（n）より速い場合、O（1）アルゴリズムよりもO（n）アルゴリズムを選択する場合の例すべてのn、O（1）がO（n）よりも速い場合、O（1）上でO（n）を選択しますか？

2016-10-27 D.Life

はい、そうです。 – jonrsharpe

1つの例は、 O（n）はそうではないのに、たくさんの記憶があります。パフォーマンスに比べてメモリが重要です。

2016-10-27 21:05:48 Arashsoft

（_Please_関数の漸近的な振る舞いの表記に注意してください_small o_は_argumentが厳密により大きい_を意味します - o（1）のアルゴリズムは厳密に一定時間内に終了する必要があります）アルゴリズムはO（1）メモリにのみ触れることができます。あなたの推論は、O（n）以上のO（n²）に対して有効です。 – greybeard

@greybeard、私はあなたの意見を理解していますが、私はこの答えが有効だと思います。両方のアルゴリズムがO（1）メモリを使用すると仮定します。しかし、o（n）は1バイトを使用し、o（1）アルゴリズムは1000バイトを使用します。 – Arashsoft

@greybeardが「big-O」（https：// en）の代わりに[little-o]（https://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations）を使用している、 .wikipedia.org/wiki/Big_O_notation）。彼らは同じものではありません。 –

多くの場合、実際のデータは、時間の複雑さがより悪いアルゴリズムに役立ちます。たとえば、ほぼソートされたデータでは、O（n^2）時間で実行されるバブルソートが高速になることがよくあります。多くの場合、一定の要因によってアルゴリズムが遅すぎて実用的にならないことがあります。 big-Oは、即時ではなく、制限内でより効率的なものを扱うことを忘れないでください。定数が10000000のO（1）アルゴリズムは、nの定数係数が1のO（n）アルゴリズムよりも大幅に遅くなります。< 10000000の場合

出典

2016-10-27 21:28:30 superlizardmo

無視することを選択した 'for all of'の一部がなければならない。 – greybeard

@greybeard質問者がO（1）アルゴリズムとO（n）アルゴリズムのどちらを測定したのか、O *（1）が常にO（n）未満であるのかどうかはわかりません。それは非常によく言われていない質問です。 –

（@MarkRansom Big-O-notationの紹介の直後に私は課題になる） – greybeard

すべてのn、O（1）がO（n）よりも速い場合、O（1）上でO（n）を選択しますか？

答えて

関連する問題