c - 配列の最大値と最小値

Question

n個の数の配列が与えられます。ここでnは偶数です。これらのn個の数の最大値と最小値を決定する必要があります。必要な比較を知る必要がありますか？

Answer 1

3*n/2-2それは比較を使用して行うことができます。

についてn == 2は、2つの数値を比較するだけです。ここで、最初のn-2数値に最小値と最大値があるとします。残りの2つの数値を比較してから、大きい方の数値を前の最大値と比較し、小さい方の数値を前の最小値と比較します。

Answer 2

O(n) 時間で実行できます。

参照用にこのリンクをチェックアウトできます

Answer 3

1.5nソートされていない配列の場合、近似比較で実行できます。min配列の要素のペアを比較し、と localを格納することでそれを行うことができますmax。n/2(ローカル) 最大値と最小値を見つけるために比較を行いましn/2た。nしたがって、このフェーズの合計。

ここで、ローカルの最大値と最小値を調べて、グローバルな最大値と最小値を見つけます。これもn/2比較対象になります。したがってn + n / 2 = 1.5n。

配列がソートされている場合、最小の数値は位置 0 にあり、最大の数値は位置 N - 1 にあるため、比較しなくても見つけることができます。