|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 11 Apr 2002 21:40:02
To : Sergiy Kanilo
Subject : Re: Поиск
--------------------------------------------------------------------------------
Однажды 09-Apr-02 в 20:38 Sergiy Kanilo (via gate)
написал Oleg I. Khovayko по поводу
-=- Re: Поиск -=-
>> А зачем же сравнивать "каждый-с-каждым"? Если список отсортирован, то
SK> каждый
>> элемент надо сравнить только с предыдущим (ну или последующим). И все!
>> То есть { число сравнений = N - 1 }, где N - число элементов в твоем
SK> списке.
>> И это оптимальное решение...
SK> Если в последовательности встречаются большие группы одинаковых
SK> элементов, то после нахождения пары одинаковых элементов можно
SK> начинать прыгать через элементы с увеличивающимся шагом 2,4,8, и т.д,
SK> и если повторяющихся элементов много - то этим можно выиграть
SK> несколько сравнений.
SK> Так напимер, в коайнем случае, если все элементы одинаковы, число
SK> сравнений пропорционально lnN.
В таком случае еще одно "улучшение": первый элемент надо сразу сравнивать с
последним, тогда "в крайнем случае" число сравнений будет =1. :)
PS. При сравнении алгоритмов принято исходить из наихудшего или среднего
случаев, но никак не из наилучшего. А в наихудшем, кстати, добавляется еще одна
гадость - возможность отката, так что общее количество операций будет (в
наихудшем случае) больше.
До свидания, в 20:57 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Re: Поиск |
Oleg I. Khovayko |
09 Apr 2002 19:13:51 |
 Re: Поиск |
Sergiy Kanilo |
09 Apr 2002 20:38:43 |
  Re: Поиск |
Sergey Andrianov |
11 Apr 2002 21:40:02 |
 Re: Поиск |
Sergiy Kanilo |
14 Apr 2002 22:00:34 |
|
Re^2: Поиск |
Alexey Zhivotov |
10 Apr 2002 11:04:38 |
|
|
