アルゴリズムの下限を計算していますか？

Question

私は大理石の問題の下限を見つけようとしていますが、問題はあります。

大理石があります。大理石が1つあります。それよりも軽い大理石が1つあります。または、すべてが等しくなることがあります。

私は標準的な計量問題から、より軽い大理石を見つけるための下限はO（log3 n）であることを知っています。

しかし、この場合、すべての大理石が等しい場合は、下限が変更されますか？

下限は、解決できる最良のケースと同じですか？

Answer 1

これは一般的な問題の下限を変更しません。大理石の1つがの場合はと軽いので、O（log3 n）の計量が必要になります。

入力のために、より迅速に行うことができ、可能な限り速い一般的なアルゴリズム（つまり、すべての法的入力に対して機能するアルゴリズム）がO（log3 n）

これは、O（n）ですでにソートされた入力を検出できるという事実にもかかわらず、比較ベースソートがO（n * log2 n）の下限に類似しています。