ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм
25 сообщений из 30, страница 1 из 2
  1  все
Алгоритм
    #33980724
Емил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Емил
Участник
Дан массив или файл с длиной N елементов.
(N предположително очень болшоe)
Массив/файл неупорядочен (несортирован).
Надо ответит на вопрос: есть ли дубирован елемент
т.е елемент который встречается более одного раза.
Неважно какой точно елемент, а просто ест или нет дублаж.

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

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

Сложность - O(N * log2(N) / 2) если вероятность распределения элеменотов нормальная.
...
Рейтинг: 0 / 0
12.09.2006, 13:35
| Ответить | Цитировать | Написать  
Алгоритм
    #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:24
| Ответить | Цитировать | Написать  
Алгоритм
    #33981593
Den_di
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Den_di
Участник
тут просто: имееи сумму n+(n-1)+(n-2)+2 -> n*(n-1)/2 что имеет сложность O(n^2)
...
Рейтинг: 0 / 0
12.09.2006, 16:33
| Ответить | Цитировать | Написать  
Алгоритм
    #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:21
| Ответить | Цитировать | Написать  
Алгоритм
    #33982287
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
Емилесть ли алгоритм с меншей сложности чем О(N*N) ?
Зависит от. Например, битовая карта, если удастся ее применить, даст сложность O(N). Radix sort, если для него хватит оперативки, также даст O(N) (если, конечно, мне не изменяет память).

k-nikeНе могу написать формулу сложности алгоритма, но по-моему вариант когда: ....... будет гораздо быстрее чем вариант с сортировкой.
"По-моему" - вещь хорошая, но ей хорошо было бы быть верной или хотя бы хоть чем-нибудь подкрепленной.
...
Рейтинг: 0 / 0
12.09.2006, 19:54
| Ответить | Цитировать | Написать  
Алгоритм
    #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, 21:04
| Ответить | Цитировать | Написать  
Алгоритм
    #33982431
k-nike2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k-nike2
Гость
softwarer k-nikeНе могу написать формулу сложности алгоритма, но по-моему вариант когда: ....... будет гораздо быстрее чем вариант с сортировкой.
"По-моему" - вещь хорошая, но ей хорошо было бы быть верной или хотя бы хоть чем-нибудь подкрепленной.
"По-моему" на то оно и по-моему, потому что я так думаю (у меня интуиция, если хотите). Я ничего на 100% не утверждал, т.к. не умею считать сложность алгоритма.
Если вы в этом разбираетесь, оценили бы сложности этих алгоритмов и доказали бы мне прав я или нет.
...
Рейтинг: 0 / 0
12.09.2006, 22:37
| Ответить | Цитировать | Написать  
Алгоритм
    #33982575
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
Емил
есть ли алгоритм с меншей сложности чем О(N*N) ?
1)хэш мап размером порядка N и цепочкой исключений.. по сути N операций..

2)как вариант хэш мап c размером << N и отсортированной цепочкой исключений.
в районе N Log2(N/HashSize) операций будет. усреднённо оптимальный вариант для всех крайних случаев.
...
Рейтинг: 0 / 0
13.09.2006, 00:36
| Ответить | Цитировать | Написать  
Алгоритм
    #33982589
Фотография Палестинец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Палестинец
Участник
а. ну учитывая архитектурные особенности x86 - сортировать исключения не надо..
выбираем размер хэша наиболее возможный для данной задачи по памяти и всё..
...
Рейтинг: 0 / 0
13.09.2006, 00:44
| Ответить | Цитировать | Написать  
Алгоритм
    #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, 08:24
| Ответить | Цитировать | Написать  
Алгоритм
    #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:07
| Ответить | Цитировать | Написать  
Алгоритм
    #33983038
Фотография k-nike
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k-nike
Участник
Вот это похоже на правду:
Den_din*(n-1)/2

А как из верхнего это получилось?
Den_diчто имеет сложность O(n^2)
...
Рейтинг: 0 / 0
13.09.2006, 10:10
| Ответить | Цитировать | Написать  
Алгоритм
    #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:21
| Ответить | Цитировать | Написать  
Алгоритм
    #33983711
Фотография ScareCrow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ScareCrow
Участник
>но сама сложност сортировки будеть
еквивалентна примеру выше.
во блин.. а мужики (Хоар и Ко) и не знают..


Posted via ActualForum NNTP Server 1.3
...
Рейтинг: 0 / 0
13.09.2006, 12:50
| Ответить | Цитировать | Написать  
Алгоритм
    #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:07
| Ответить | Цитировать | Написать  
Алгоритм
    #33984429
Фотография k-nike
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k-nike
Участник
softwarerплюс дополнительные проблемы в случае, если данные не влезают в память.
Интересно какие там еще данные требуются кроме самого массива?
...
Рейтинг: 0 / 0
13.09.2006, 15:14
| Ответить | Цитировать | Написать  
Алгоритм
    #33984487
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin
Участник
авторПри сортировке реально получить O(N). N log N - это асимптотическая оценка для алгоритмов на основе функций сравнения.

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

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

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

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

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

Интересно.

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


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