|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 07 Aug 2003 10:51:06
To : Oleg Khovayko [SPAM trap - don't re
Subject : Re: поиск локальных max и min в массиве
--------------------------------------------------------------------------------
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 и обрабатывает, если явно не потребовано иного...)
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
