Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм / 25 сообщений из 30, страница 1 из 2
  1  все
12.09.2006, 13:19
    #33980724
Емил
Емил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Дан массив или файл с длиной N елементов.
(N предположително очень болшоe)
Массив/файл неупорядочен (несортирован).
Надо ответит на вопрос: есть ли дубирован елемент
т.е елемент который встречается более одного раза.
Неважно какой точно елемент, а просто ест или нет дублаж.

Очевидное решение сравнят каждый с каждый елемент
приводить к числу сравнений которое пропорционално N*N
т.е. сложност алгоритма О(N*N).

Так вопрос в том:
есть ли алгоритм с меншей сложности чем О(N*N) ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.09.2006, 13:35
    #33980814
Pavel Kilevatyh
Pavel Kilevatyh
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Эта задача уже обсуждалась.
1. Отсортировать данные.
2. Просмотреть список на наличие двух одинаковых элементов стоящих рядом.

Сложность - O(N * log2(N) / 2) если вероятность распределения элеменотов нормальная.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.09.2006, 16:24
    #33981541
k-nike
k-nike
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Не могу написать формулу сложности алгоритма, но по-моему вариант когда:
Код: plaintext
1.
2.
3.
4.
 1 -ый эл. сравнивается со  2 -м ... N-м
 2 -ой эл. сравнивается с  3 -м ... N-м
 3 -ый эл. сравнивается с  4 -м ... N-м
и т.д.
будет гораздо быстрее чем вариант с сортировкой.

...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.09.2006, 16:33
    #33981593
Den_di
Den_di
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
тут просто: имееи сумму n+(n-1)+(n-2)+2 -> n*(n-1)/2 что имеет сложность O(n^2)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.09.2006, 19:21
    #33982243
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Den_diтут просто: имееи сумму n+(n-1)+(n-2)+2 -> n*(n-1)/2 что имеет сложность O(n^2)
вообще-то O((n-1)!)
сортировка - до Nlog(N)

какой размер элемента , если short и ниже, легко.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.09.2006, 19:54
    #33982287
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Емилесть ли алгоритм с меншей сложности чем О(N*N) ?
Зависит от. Например, битовая карта, если удастся ее применить, даст сложность O(N). Radix sort, если для него хватит оперативки, также даст O(N) (если, конечно, мне не изменяет память).

k-nikeНе могу написать формулу сложности алгоритма, но по-моему вариант когда: ....... будет гораздо быстрее чем вариант с сортировкой.
"По-моему" - вещь хорошая, но ей хорошо было бы быть верной или хотя бы хоть чем-нибудь подкрепленной.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.09.2006, 21:04
    #33982349
contr
contr
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Aklin Den_diтут просто: имееи сумму n+(n-1)+(n-2)+2 -> n*(n-1)/2 что имеет сложность O(n^2)
вообще-то O((n-1)!)
Блин, отцы, спасайте - всю голову сломал, а (n-1)! не получается... Сплошной N 2 ...
Откуда такая оценка?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
12.09.2006, 22:37
    #33982431
k-nike2
k-nike2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
softwarer k-nikeНе могу написать формулу сложности алгоритма, но по-моему вариант когда: ....... будет гораздо быстрее чем вариант с сортировкой.
"По-моему" - вещь хорошая, но ей хорошо было бы быть верной или хотя бы хоть чем-нибудь подкрепленной.
"По-моему" на то оно и по-моему, потому что я так думаю (у меня интуиция, если хотите). Я ничего на 100% не утверждал, т.к. не умею считать сложность алгоритма.
Если вы в этом разбираетесь, оценили бы сложности этих алгоритмов и доказали бы мне прав я или нет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 00:36
    #33982575
Палестинец
Палестинец
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Емил
есть ли алгоритм с меншей сложности чем О(N*N) ?
1)хэш мап размером порядка N и цепочкой исключений.. по сути N операций..

2)как вариант хэш мап c размером << N и отсортированной цепочкой исключений.
в районе N Log2(N/HashSize) операций будет. усреднённо оптимальный вариант для всех крайних случаев.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 00:44
    #33982589
Палестинец
Палестинец
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
а. ну учитывая архитектурные особенности x86 - сортировать исключения не надо..
выбираем размер хэша наиболее возможный для данной задачи по памяти и всё..
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 08:24
    #33982779
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
contr Aklin Den_diтут просто: имееи сумму n+(n-1)+(n-2)+2 -> n*(n-1)/2 что имеет сложность O(n^2)
вообще-то O((n-1)!)
Блин, отцы, спасайте - всю голову сломал, а (n-1)! не получается... Сплошной N 2 ...
Откуда такая оценка?

1-ый только с n-1
второй с n-2
третий с n-3
суммарна сложность - т.к. цикл по n то перемножить.

но дел не в этом.
можно реально получить сложность N*log(N) при сортировке. много алгоритмов дают такую оценку.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 10:07
    #33983033
k-nike
k-nike
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Aklin contr Aklin Den_diтут просто: имееи сумму n+(n-1)+(n-2)+2 -> n*(n-1)/2 что имеет сложность O(n^2)
вообще-то O((n-1)!)
Блин, отцы, спасайте - всю голову сломал, а (n-1)! не получается... Сплошной N 2 ...
Откуда такая оценка?

1-ый только с n-1
второй с n-2
третий с n-3
суммарна сложность - т.к. цикл по n то перемножить.

Не знаю какая, но все равно не O((n-1)!).
Согласитесь, что сложность O((n-1)!) сложнее O(n 2 ), а последняя справедлива для цикла в цикле, с одним и тем же числом итерраций, т.е. n .
Или я что-то не так понимаю?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 10:10
    #33983038
k-nike
k-nike
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Вот это похоже на правду:
Den_din*(n-1)/2

А как из верхнего это получилось?
Den_diчто имеет сложность O(n^2)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 12:21
    #33983584
Емил
Емил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
Спасибо за коментарии.
Но к сожелению не увидел ответ который хотел - более бистрый алгоритм.

Во первых задача поставлена "академично" т.е. не
имеет значение язык или процессор или что то другое -
интересен алгоритм сам по себя.
Елементы масива/файла могут быть целые числа, нецелые,
строки или что угодно (но конечно дефинирована операция
"сравнение двух елементов").

Так в первом посте я написал что сложност О(N*N)
или O(n^2)

например (на паскале)
Код: plaintext
1.
2.
3.
for cnt1:= 1  to N- 1  do
  for cnt2:=cnt1+ 1  to N do
     if array[cnt1]=array[cnt2] then ... {конец - нашли дубикат}

Количество сравнении будет от одного
(если совпадут array[1] i array[2]) до максимум
N*(N-1)/2 если нет дубликатов.

а так как N*(N-1)/2 есть (1/2)*N^2+... более мелкие члены которые
отбрасиваем при большом N, а (1/2) ето константа - тоже отбрасиваем
тоест сложност алгоритма есть O(N^2)

Если сортировать данные предварително то нахождение
елемента будет быстро, но сама сложност сортировки будеть
еквивалентна примеру выше. Так что не имеет смысл.

Ну ето почти очевидно (так думаю) что если есть два одинаковых
елемента , то что бы их найти надо сравнит каждые два.
В худшем случае ето ~ N*N.
Но вопреки моей убеждености - решил спросить - а вдруг кто то
придумал что то гениальное :) вед не я же самый умный :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 12:50
    #33983711
ScareCrow
ScareCrow
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
>но сама сложност сортировки будеть
еквивалентна примеру выше.
во блин.. а мужики (Хоар и Ко) и не знают..


Posted via ActualForum NNTP Server 1.3
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 15:07
    #33984410
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
k-nike2"По-моему" на то оно и по-моему, потому что я так думаю (у меня интуиция, если хотите).
Как раз не хочу. Есть старая истина: "информация - мать интуиции".

k-nike2Если вы в этом разбираетесь, оценили бы сложности этих алгоритмов и доказали бы мне прав я или нет.
Оценка уже приведена. Для Вашего алгоритма - O(N*N), плюс дополнительные проблемы в случае, если данные не влезают в память. Для сортировки - O(N * log N) в общем случае и O(N), если выполняются некоторые дополнительные условия.

Что же касается второй части Вашего предложения - поверьте, Вы способны генерировать неверные гипотезы с куда большей скоростью, нежели я способен их опровергать. Читайте книжки.

Aklinможно реально получить сложность N*log(N) при сортировке. много алгоритмов дают такую оценку.
При сортировке реально получить O(N). N log N - это асимптотическая оценка для алгоритмов на основе функций сравнения.

ЕмилНо к сожелению не увидел ответ который хотел - более бистрый алгоритм.
Названия алгоритмов я дал. Расписывать, извините, не буду.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 15:14
    #33984429
k-nike
k-nike
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
softwarerплюс дополнительные проблемы в случае, если данные не влезают в память.
Интересно какие там еще данные требуются кроме самого массива?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 15:29
    #33984487
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
авторПри сортировке реально получить O(N). N log N - это асимптотическая оценка для алгоритмов на основе функций сравнения.

прошу разъяснить: как ты хочешь получить A*N причем A много меньше N (? при N скажем > 100 ?)

никогда не реально получить их квадрата линейную функцию.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 15:36
    #33984530
LeonM
LeonM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
на практике сортировка не требуется: значения заносятся в таблицу с уникльным индексом до первой ошибки. алгоритм сортировки при этом реализован в индексе.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 15:50
    #33984584
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
перечитал сабж.
N да еще 1*N а не O(..)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 15:57
    #33984628
Den_di
Den_di
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
есть почти линейный алгоритм :)
и скажите точно, где ищем дубли и какой у них тип(размер в байтах)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 16:15
    #33984710
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
k-nikeИнтересно какие там еще данные требуются кроме самого массива?
Которые "или файл" и "очень большой". Данные очень большого файла запросто могут не влезть в память.

LeonMна практике сортировка не требуется: значения заносятся в таблицу с уникльным индексом до первой ошибки. алгоритм сортировки при этом реализован в индексе.
На практике к этому добавляется эффективное хранение и получается упомянутый мной выше алгоритм битовой карты.

Aklinпрошу разъяснить: как ты хочешь получить A*N причем A много меньше N (? при N скажем > 100 ?)

никогда не реально получить их квадрата линейную функцию.
Признаться, не понял этого пассажа, но это не отменяет того факта, что я назвал два алгоритма с асимптотикой O(N).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
13.09.2006, 16:24
    #33984764
Aklin
Aklin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
softwarer
сабж берет не более
N считыван ий из файла + не более N сравнений
+вывод на экран.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.09.2006, 10:27
    #33986191
man_555
man_555
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
LeonMна практике сортировка не требуется: значения заносятся в таблицу с уникльным индексом до первой ошибки. алгоритм сортировки при этом реализован в индексе.

Интересно.

Для этого надо 1 раз пройтись по массиву, а для сбалансированного бинарного дерева сложность вставки составляет log(N).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
14.09.2006, 11:33
    #33986421
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Алгоритм
man_555
И получите те же самые O (N * log N)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм / 25 сообщений из 30, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]