ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм
30 сообщений из 30, показаны все 2 страниц
  все  
Алгоритм
    #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
| Ответить | Цитировать | Написать  
Алгоритм
    #33987459
k-nike2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k-nike2
Гость
softwarer k-nikeИнтересно какие там еще данные требуются кроме самого массива?
Которые "или файл" и "очень большой". Данные очень большого файла запросто могут не влезть в память.
Хотите сказать для сортировки массива "или файл" или "очень большой" не важно? Я далеко не спец, но у меня очень большие сомнения по этому поводу. К тому же не обязательно читать файл целиком в обоих случаях.
Еще про сортировку массива почитал тут , конкретная таблица тут . В худшем случае сложность сортировки массива О(N 2 ), т.е. такая же!!!
А в среднем О(N*log2(N)).
Остается посчитать среднюю сложность нелюбимого вами метода для полного понимания происходящего.
...
Рейтинг: 0 / 0
14.09.2006, 14:53
| Ответить | Цитировать | Написать  
Алгоритм
    #33988752
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
k-nike2Хотите сказать для сортировки массива "или файл" или "очень большой" не важно?
Смотря какой алгоритм. Скажем, для той же битовой карты - не важно. Популярность quicksort во многом обусловлена тем, что алгоритм отлично подходит для систем с виртуальной памятью.

k-nike2К тому же не обязательно читать файл целиком в обоих случаях.
Это не важно. Если читать файл целиком, сложность чтения O(N). Если требуется прочитать в среднем пол-файла, сложность чтения опять-таки O(N). И если не иметь данных о внутренней структуре файла, эту оценку улучшить не удастся.

k-nike2В худшем случае сложность сортировки массива О(N 2 ), т.е. такая же!!!
Да, выборка из трех алгоритмов позволяет сделать такой вывод.

Для битовой карты в худшем случае сложность O(N). Такая же?

k-nike2Остается посчитать среднюю сложность нелюбимого вами метода для полного понимания происходящего.
Что ж, считайте. Вы двигаетесь в правильном направлении.
...
Рейтинг: 0 / 0
14.09.2006, 20:28
| Ответить | Цитировать | Написать  
Алгоритм
    #33988772
k-nike2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k-nike2
Гость
Напоминаю с чего все началось:
softwarer k-nikeНе могу написать формулу сложности алгоритма, но по-моему вариант когда:
Код: plaintext
1.
2.
3.
 1 -ый эл. сравнивается со  2 -м ... N-м
 2 -ой эл. сравнивается с  3 -м ... N-м
 3 -ый эл. сравнивается с  4 -м ... N-м
и т.д.
будет гораздо быстрее чем вариант с сортировкой .
"По-моему" - вещь хорошая, но ей хорошо было бы быть верной или хотя бы хоть чем-нибудь подкрепленной.
Я свои слова, как мне кажется, подкрепил. А про битовую карту я ничего не говорил и ни с чем ее не сравнивал. Или вы хотите сказать, что битовая карта и есть сортировка? Тогда я, конечно, не прав, но я имел ввиду обычную сортировку массива, типа, пузырьковой.
...
Рейтинг: 0 / 0
14.09.2006, 20:47
| Ответить | Цитировать | Написать  
Алгоритм
    #33988783
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
k-nike2Напоминаю с чего все началось:
Я помню. Это по сути пузырек, сложность O(N 2 ).

k-nike2Я свои слова, как мне кажется, подкрепил.
Чем? Вы назвали три алгоритма, у которых сложность в наихудшем случае такая же, какая у Вас в наилучшем. У одного из них такая же сложность в среднем случае, из-за чего его используют только очень ленивые и глупые студенты (глупые - потому что не способны списать откуда-нибудь более удачную реализацию).

k-nike2Или вы хотите сказать, что битовая карта и есть сортировка?
Битовая карта в принципе является алгоритмом сортировки. В случае конкретной задачи сортировка нам неинтересна, важен факт наличия дублей, который определяется аналогичным способом со сложностью O(N).

k-nike2Тогда я, конечно, не прав, но я имел ввиду обычную сортировку массива, типа, пузырьковой.
И? quicksort даст N log N. radix sort даст N. То и другое является "обычными сортировками".
...
Рейтинг: 0 / 0
14.09.2006, 20:58
| Ответить | Цитировать | Написать  
Алгоритм
    #33988911
k-nike2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k-nike2
Гость
softwarerВы назвали три алгоритма, у которых сложность в наихудшем случае такая же, какая у Вас в наилучшем.
Я смотрю мы все о разном. Я-то с дуру под сложность скорость подразумеваю, но как выяснилось скорость от сложности мало зависит (+/- бесконечность).
см. ссылку вышеОсновным недостатком O-функций является их черезмерная грубость. Если алгоритм А выполняет некоторую задачу за 0.001*N с, в то время как для ее же решения с помощью алгоритма В требуется 1000*N с, то В в миллион раз быстрее, чем А. Тем не менее А и В имеют одну и ту же временную сложность O(N).
К тому же, здесь уже говорилось, в том числе и вами, что битовую карту как и некоторые алгоримы сортировки можно применить не для всех данных, а автор имел ввиду непосредственно алгоритм. Я понимаю, что числа легче сравнивать, чем, например, строки.

softwarerиз-за чего его используют только очень ленивые и глупые студенты (глупые - потому что не способны списать откуда-нибудь более удачную реализацию).
А я наивно считал, что ленивые и глупые списывают...
...
Рейтинг: 0 / 0
15.09.2006, 00:18
| Ответить | Цитировать | Написать  
30 сообщений из 30, показаны все 2 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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