 |
|
Модераторы: Poseidon |
 
|
|
[Алгоритм] Наименьшее натуральное число, не входящее в последовательность. 
| fsherstobitov |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 12.9.2008 Репутация: нет Всего: нет |
Дан массив натуральных чисел. Необходимо найти наименьшее натурально число, не входящее в данный массив. Алгоритм должен выполняться за О(n).
|
|||
|
||||
Загрузка ...
| Фантом |
|
|||
 Вы это прекратите!  Профиль Группа: Участник Клуба Сообщений: 1516 Регистрация: 23.3.2008 Репутация: 7 Всего: 49 |
Заводим массив 1:n из булевских переменных B, весь забитый, например, false. Проходимся один раз по исходному массиву, для каждого элемента со значением q устанавливая в булевском массиве элемент B[q] в true (если q>n, то ничего не делаем).
Затем проходимся по булевскому массиву и ищем номер первого элемента, имеющего значение false. Это и есть ответ. |
|||
|
||||
| bems |
|
|||
 Эксперт Профиль Группа: Комодератор Сообщений: 3400 Регистрация: 5.1.2006 Репутация: 0 Всего: 88 |
Фантом, это О(2n). Нет?
Это сообщение отредактировал(а) bems - 19.6.2010, 19:47 -------------------- Обижено школьников: 8 |
|||
|
||||
| Фантом |
|
|||
|
Вы это прекратите! Профиль Группа: Участник Клуба Сообщений: 1516 Регистрация: 23.3.2008 Репутация: 7 Всего: 49 |
И нет, и да.  Смысл O-символики при оценке сложности алгоритма (во всех других случаях, впрочем, тоже) в том, что если количество операций алгоритма зависит от n как f(n), то сложность алгоритма O(g(n)) должна быть такой, чтобы предел f(n)/g(n) при n, стремящемся к бесконечности, оказался ненулевым и конечным.Как следствие, O(n) и O(2*n) попросту ничем не отличаются (и второй вариант при описании асимптотической сложности алгоритмов не используется). Это, кстати, логично не только с формальной точки зрения: поскольку мы не знаем точно, какое количество тактов процессора будет использовано для выполнения той или иной операции, то сравнивать линейные по n алгоритмы по коэффициенту малоосмысленно - вполне возможно, что какой-либо "однопроходный" алгоритм за счет большей трудоемкости обработки одной ячейки массива будет выполняться дольше, чем мой "двупроходный". Другое дело, что бывают случаи, когда для алгоритма, например, с O(n^3) для некоторого диапазона n на некоторой определенной архитектуре можно получить более быструю реализацию, чем для другого алгоритма с O(n^2), но это уже совсем другая задача, для которой нужно конкретизировать и "стоимость" элементарных операций, и максимальные n, для которых нужно найти эффективное решение. |
|||
|
||||
| bems |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 3400 Регистрация: 5.1.2006 Репутация: 0 Всего: 88 |
К стати в большинстве случаев подойдет найти минимум массива и отнять единицу. Есть мысли как адаптировать это чтоб работало всегда?
-------------------- Обижено школьников: 8 |
|||
|
||||
| Фантом |
|
|||
|
Вы это прекратите! Профиль Группа: Участник Клуба Сообщений: 1516 Регистрация: 23.3.2008 Репутация: 7 Всего: 49 |
Нет, не годится. Допустим, массив заполнен числами 10,11,12,13 и т.д. Ответ должен равняться 1, а не 9. Собственно говоря, тут возможны только два варианта - либо минимум не равен 1, и тогда ответ - единица. Либо минимум равен 1 и это не дает вообще никакой информации об ответе. |
|||
|
||||
| bems |
|
|||
|
Эксперт Профиль Группа: Комодератор Сообщений: 3400 Регистрация: 5.1.2006 Репутация: 0 Всего: 88 |
-------------------- Обижено школьников: 8 |
|||
|
||||
| fsherstobitov |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 7 Регистрация: 12.9.2008 Репутация: нет Всего: нет |
Спасибо за ответ! |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.1140 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |