|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrei Koulik 2:5020/400 07 Aug 2003 13:35:02
To : Evgenij Masherov
Subject : Re: поиск локальных max и min в массиве
--------------------------------------------------------------------------------
Evgenij Masherov wrote:
> Thu Aug 07 2003 01:20, Oleg Khovayko [SPAM trap - don't re wrote to Evgenij
> Masherov:
>
>
> >> Максимум:
>
> OKStd> 1 2
>
> >> (x[i]>x[i-1]) AND (x[i]>x[i+1])
> >> (поскольку для выбранного формата вероятность совпадения значений
> >> достаточно высока, одно из неравенств лучше сделать нестрогим)
> >> Минимум:
>
> OKStd> 3 4
>
> >> (x[i]<x[i-1]) AND (x[i]<x[i+1])
> >>
>
> OKStd> Hу этот пример выше - прямо как из школьных уроков информатики.
> OKStd> Это же неинтересно, когда к каждому элементу входного массива
> OKStd> в среднем шесть раз обращаться приходится!
>
> OKStd> Почему 6? Да потому, что операции 1,3 выполняются со 100% вероятностью
> OKStd> дважды для каждого элемента массива (ибо i шагает подряд), да еще с
> OKStd> 50% вероятностью по 2 раза будут выполнены операции сравнения 2,4.
>
> OKStd> Итого выходит 6 обращений. Да еще как я понимаю, неявно предлагается
> OKStd> на каждой итерации проверять на конец массива....
>
> Hу, для критичной скорости делается вложенные условия, так что при
> невыполнении последующего предыдущее не проверяется (сюрприз! сюрприз!
> Компилятор именно так AND и обрабатывает, если явно не потребовано иного...)
Извиняюсь что влез, но хочу заметить, что Олег указал это:
OKStd> да еще с 50% вероятностью
OKStd> по 2 раза будут выполнены операции сравнения 2,4.
От сбя хочу добавить, что укзанные Вами метод не предусматривает
повторяющиеся значения в массиве (вне зависимости от строгости условий).
пример:
10,10,10,11,11,11,0,0,0,22,22
>
> Евгений Машеров АКА СанитарЖеня
>
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
