Вот тут знакомый задачку дал: Как наиболее оптимально найти в неупорядоченном массиве элемент, который встречается в нем только один раз. И какова сложность данного решения?
Как вы думаете, за сколько шагов можно выполнить задачу?
Re: Поиск элемента в массиве, который встречается один раз
Здравствуйте, ankorol, Вы писали:
A>Здравствуйте, DenXX, Вы писали: A>... A> Если все остальные элементы встречаются четное кол-во раз, то за О(n) — просто проксорить все.
Ой, я забыл написать, что элементов, встречающихся один раз может быть несколько. А найти надо первый.
Re[2]: Поиск элемента в массиве, который встречается один ра
От:
Аноним
Дата:
08.06.08 17:37
Оценка:
Здравствуйте, subdmitry, Вы писали:
S>Хэширование — O(n) время O(n) память. S>Сортировка массива — O(n log n) время O(1) память.
А расскажите как вы отсортируете за O(n log n) времени, при O(1) памяти.
Re[3]: Поиск элемента в массиве, который встречается один ра
Здравствуйте, Аноним, Вы писали:
А>А расскажите как вы отсортируете за O(n log n) времени, при O(1) памяти.
См. пирамидальную сортировку.
Хотя с точки зрения практики O(log n) весьма недалеко от O(1). Возникают даже всякие вопросы, типа того, что индексная переменная, которая бегает по массиву, тоже занимает не менее O(log n) памяти.
And if you listen very hard the alg will come to you at last.
Re[4]: Поиск элемента в массиве, который встречается один ра
Здравствуйте, subdmitry, Вы писали:
S>Здравствуйте, Аноним, Вы писали:
А>>А расскажите как вы отсортируете за O(n log n) времени, при O(1) памяти.
S>См. пирамидальную сортировку.
S>Хотя с точки зрения практики O(log n) весьма недалеко от O(1). Возникают даже всякие вопросы, типа того, что индексная переменная, которая бегает по массиву, тоже занимает не менее O(log n) памяти.
Как одна переменная может занимать logn памяти без использования рекурсии? Массив что ли?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[5]: Поиск элемента в массиве, который встречается один ра
Здравствуйте, PaulMinelly, Вы писали:
PM>Как одна переменная может занимать logn памяти без использования рекурсии? Массив что ли?
Для индексации массива из 256 элементов нужна однобайтовая переменная, из 65к — двухбайтовая, для массива из n элементов — Сеil(Log2(n)/8) — байтовая
Конечно, это формализм, и для практических целей не имеет значения.
Re[6]: Поиск элемента в массиве, который встречается один ра
PM>>Как одна переменная может занимать logn памяти без использования рекурсии? Массив что ли?
MBo>Для индексации массива из 256 элементов нужна однобайтовая переменная, из 65к — двухбайтовая, для массива из n элементов — Сеil(Log2(n)/8) — байтовая MBo>Конечно, это формализм, и для практических целей не имеет значения.
Если дальше пойти то С# можно проиндексировать массив содержащий более 2^64 элементов?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[5]: Поиск элемента в массиве, который встречается один ра
Здравствуйте, Vamp, Вы писали:
S>>Хэширование — O(n) время O(n) память. V>Это при условии идеальной хеш-функции. А где ее найти?
Например, в книге CLR (Кормен и Ко).
Еще можно взять CRC. Практически идеально. Остается разве что случай преднамеренной генерации хакерами данных с одинаковым хэшем в целях завешивания машины. Тоже лечится. Например, наложением на хэшируемые данные значения времени на компьютере в момент выполнения программы.
And if you listen very hard the alg will come to you at last.
Re[4]: Поиск элемента в массиве, который встречается один ра
