|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 07 Aug 2003 14:45:09
To : Andrei Koulik
Subject : Re: поиск локальных max и min в массиве
--------------------------------------------------------------------------------
Thu Aug 07 2003 13:35, Andrei Koulik wrote to Evgenij Masherov:
>> 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 и обрабатывает, если явно не потребовано
>> иного...)
AK> Извиняюсь что влез, но хочу заметить, что Олег указал это:
OKStd>> да еще с 50% вероятностью
OKStd>> по 2 раза будут выполнены операции сравнения 2,4.
Hу, поставить дополнительное else не трудно... И тогда после найденного
максимума поиск минимума не делается...
AK> От сбя хочу добавить, что укзанные Вами метод не предусматривает
AK> повторяющиеся значения в массиве (вне зависимости от строгости условий).
AK> пример:
AK> 10,10,10,11,11,11,0,0,0,22,22
А вот здесь уже вопрос соглашения. Скажем, если второе сравнение сделать
нестрогим - то за максимум будет принято первое появление 11 и 22, за минимум
- первое появление 0 (и больше никакие). Соответствует ли это нашим ожиданиям
- вопрос к заказчику/постановщику.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
