ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
25 сообщений из 29, страница 1 из 2
  1  все
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36208911
Фотография Василий Викторович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Василий Викторович
Участник
по сабжу
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти равном N элементов?
...
Рейтинг: 0 / 0
22.09.2009, 04:47:33
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36209017
clihlt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
clihlt
Участник
Василий Викторович,

Обычный массив? Или я чегото не понял )
...
Рейтинг: 0 / 0
22.09.2009, 09:15:11
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36209035
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Василий Викторовичпо сабжу
Можно ли создать структуру с временем поиска за O(N)
Обычно ищут логарифмическое время. А у вас требования какие-то странные...
...
Рейтинг: 0 / 0
22.09.2009, 09:22:19
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36210953
Фотография Василий Викторович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Василий Викторович
Участник
в обычном (не сортированном) массиве время поиска примерно равно 0.7*O(N^2) а меня интересует время О(N) и потребление памяти равное N
...
Рейтинг: 0 / 0
22.09.2009, 16:58:43
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36210966
Фотография Василий Викторович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Василий Викторович
Участник
mayton, если можно подскажите пару тынцев на теорию для реализации за время O(LN(N))
входные данные: дан массив из 10000000 unsigned long элементов
...
Рейтинг: 0 / 0
22.09.2009, 17:02:14
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36210970
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Василий Викторовичв обычном (не сортированном) массиве время поиска примерно равно 0.7*O(N^2)Это почему? Определите точнее, о каком поиске идет речь.
...
Рейтинг: 0 / 0
22.09.2009, 17:03:56
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36210973
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Василий Викторовичmayton, если можно подскажите пару тынцев на теорию для реализации за время O(LN(N))
входные данные: дан массив из 10000000 unsigned long элементовОтсортировать. Частный случай - дерево.
...
Рейтинг: 0 / 0
22.09.2009, 17:04:53
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211172
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Василий Викторовичmayton, если можно подскажите пару тынцев на теорию для реализации за время O(LN(N))
входные данные: дан массив из 10000000 unsigned long элементов
Sort + Binary search
Гугл знает про них ВСЁ.
...
Рейтинг: 0 / 0
22.09.2009, 18:06:08
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211275
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
авторв обычном (не сортированном) массиве время поиска примерно равно 0.7*O(N^2) а меня интересует время О(N) и потребление памяти равное N

Это как же надо исхитриться чтоб в обычном неотсортированном массиве искать элемент за О(N^2)? Вот скажите, где здесь квадратичное время поиска?


Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
long FindInUnsortedArray(long arr[], long N, long value_to_be_found)
{
      for(long i =  0 ; i < N; i++)
      {
            if(arr[i] == value_to_be_found)
                     return i;
      }

      return - 1 ;
}
...
Рейтинг: 0 / 0
22.09.2009, 19:03:32
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211434
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Василий Викторович пишет:

> Можно ли создать структуру с временем поиска за O(N) и размером
> занимаемой памяти равном N элементов?

Конечно, любой массив, вектор или связный список удовлетворяет
вашим запросам.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
22.09.2009, 21:02:01
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211437
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
mikhail_n пишет:

> Это как же надо исхитриться чтоб в обычном неотсортированном массиве
> искать элемент за О(N^2)? Вот скажите, где здесь квадратичное время поиска?
>
+1

Поиск есть за
O(n) -- линейный

O(log n) -- binary search по сортированному массиву

O(1) -- хэш-таблицы

O(n*n) - не, ну можно конечно, если постараться ...
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
22.09.2009, 21:05:02
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211514
Фотография Василий Викторович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Василий Викторович
Участник
MasterZiv,

т. е. хеш самый быстрый?
...
Рейтинг: 0 / 0
22.09.2009, 22:31:20
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211519
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Василий Викторовичmayton, если можно подскажите пару тынцев на теорию для реализации за время O(LN(N))
входные данные: дан массив из 10000000 unsigned long элементов
1) Вам пригодится сортировка . Это может быть любой метод (стабильный и нестабильный, поскольку кроме сортируемых ключей данных больше нету). Можно взять быструю сортировку (она-же сортировка Хоара) или метод Шелла.

Если вы используете 32х разрядный unsigned long, то при свободном объёме оперативки 2 Гб имеет смысл сортировать и искать массивы до

(2 * 1024 * 1024 * 1024) / (32 бит = 4 байт) = 2147483648 байт / 4 байт = 536 870 912 штук элементов.

Если элементов будет больше чем макс значение 536 млн, то надо использовать дисковые методы сортировки, такие как сортировка слиянием. На сайте алголист всего-лишь скупо упоминается о том, что этот метод пригоден для дисковых файлов. И это недоработка. Сортировку слиянием также можно эффективно оптимизировать.

2) И двоичный (бинарный) поиск элемента в массиве. Его временная сложность равна порядка O(Ln(N)). Если элементы неуникальны, то после успешного найденного элемена надо сделать еще несколько итераций для того чтобы выбрать все совпадающие ключи.

Если количество уникальных элементов слишком мало (около десятка) то есть еще варианты оптимизаций поиска.
...
Рейтинг: 0 / 0
22.09.2009, 22:38:50
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211549
Фотография Василий Викторович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Василий Викторович
Участник
mikhail_n,

при M искомых элеметов сложность вашего алгоритма равна O(N*M) что равноносильно (при M=N) O(N^2) + время вызовы функций
...
Рейтинг: 0 / 0
22.09.2009, 23:11:29
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211565
Фотография Василий Викторович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Василий Викторович
Участник
mayton, спасибо за развернутый ответ :), как я понял быстрее хеша ничего нет, а за способы дисковой сортировки спасибо
...
Рейтинг: 0 / 0
22.09.2009, 23:34:16
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211572
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
авторпри M искомых элеметов сложность вашего алгоритма равна O(N*M) что равноносильно (при M=N) O(N^2) + время вызовы функций

Василий, при М искомых элементов где М порядка N, нормальные люди один раз сортируют массив за O(N*LogN) операций, а затем ищут элементы в отсортированном массиве за O(LogN) операций. Таким образом, амортизированная стоимость поиска одного элемента

(O(N*LogN) + M*O(LogN))/M = O(LogN)

при М = O(N). Что же касается случая когда М = N, то тут вообще достаточно отсортировать один раз, после этого поиск будет проходить за О(1).


Вы когда задаёте вопросы, то пожалуйста сразу оговаривайте что собираетесь искать более одного элемента, а то из вашего первого поста это далеко не очевидно.
...
Рейтинг: 0 / 0
22.09.2009, 23:41:55
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211580
mikhail_n
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikhail_n
Участник
авторЧто же касается случая когда М = N, то тут вообще достаточно отсортировать один раз, после этого поиск будет проходить за О(1).

Вот здесь глупость ляпнул, извиняюсь
...
Рейтинг: 0 / 0
22.09.2009, 23:46:38
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36211897
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Василий Викторовичmayton, спасибо за развернутый ответ :), как я понял быстрее хеша ничего нет, а за способы дисковой сортировки спасибо
Пожалуйста.

Не забывайте, что hashtable теряет свои свойства при резком приросте количества элементов. Его рекомендуют перестраивать с новой формулой хеширования. А это - накладные расходы.
...
Рейтинг: 0 / 0
23.09.2009, 10:00:36
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36213512
Фотография Гусар
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гусар
Участник
с вики:
Если отрезок имеет длину N, то найти решение с точностью до ε можно за время N\over\epsilon. Т.о. асимптотическая сложность алгоритма — O(n). В связи с малой эффективностью по сравнению с другими алгоритмами линейный поиск обычно используют только если отрезок поиска содержит очень мало элементов, тем не менее линейный поиск не требует дополнительной памяти или обработки/анализа функции, так что может работать в потоковом режиме при непосредственном получении данных из любого источника. Так же, линейный поиск часто используется в виде линейных алгоритмов поиска максимума/минимума.
...
Рейтинг: 0 / 0
23.09.2009, 19:41:00
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36213628
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Василий Викторович wrote:

>
> т. е. хеш самый быстрый?
Да, но у него есть один очень существенный недостаток:
при определённо подобранных данных поиск по хэш-таблице может
деградировать до линейного.
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
23.09.2009, 21:19:24
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36213635
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Василий Викторович wrote:

> при M искомых элеметов сложность вашего алгоритма равна O(N*M) что
> равноносильно (при M=N) O(N^2) + время вызовы функций

Василий Викторович, с тобой всё понятно. Ты просто не умеешь
считать O(). В приведённом mikhail_n алгоритме оно - O(N).
Т.е. линейное. Там как бы общего правила нет, и, конечно,
всё сложно, но конкретно в оценках операции сортировки
оценивают кол-во СРАВНЕНИЙ двух элементов.

иногда, например, для алгоритмов сортировки во внешней
памяти, оценивают кол-во ПЕРЕСТАНОВОК ЭЛЕМЕНТОВ, но
тогда это всегда оговаривается.

Так что и у тебя, в твоей формуле, видимо, должно быть
O(N) а не O(N**2).
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
23.09.2009, 21:24:31
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36213643
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
mayton wrote:

> Не забывайте, что hashtable теряет свои свойства при резком приросте
> количества элементов. Его рекомендуют перестраивать с новой формулой
> хеширования. А это - накладные расходы.

Не обязательно при резком приросте.

Дело в том, что существуют разные стратегии т.н. " обработки
переполнений ", это когда несколько элементов таблицы имеет
один и тот же хэш-код. Так вот, они бывают разные, их порядка
нескольких десятков понапридумывали в своё время. Ну, и, соответсвенно,
не для всех критичен резкий прирост (статистически равномерно размазанный
по всей таблице).

Но вот для всех хэш-функций по определению критичны такие последовательности
ключей, в которых все элементы обладают одним и тем же значением
хэш-функции. И, соответственно, искусство пользования хэш-таблицей
заключается в том, чтобы подобрать хорошую для обрабатываемых ключей
хэш-функцию.

Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
23.09.2009, 21:30:21
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36213657
RAndrew
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RAndrew
Участник
Василий Викторовичпри M искомых элеметов сложность вашего алгоритма равна O(N*M) что равноносильно (при M=N) O(N^2) + время вызовы функций

Интересная теория, а при выполнении программой операций поиска M=N^2 раз сложность алгоритма равна O(N^3) + время вызова функции.
...
Рейтинг: 0 / 0
23.09.2009, 21:38:23
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36213687
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
MasterZivНо вот для всех хэш-функций по определению критичны такие последовательности
ключей, в которых все элементы обладают одним и тем же значением
хэш-функции. И, соответственно, искусство пользования хэш-таблицей
заключается в том, чтобы подобрать хорошую для обрабатываемых ключей
хэш-функцию.
Полностью согласен, но на практике обычно используют стандартные формулы расчёта хеша. В во многих библиотеках (шаблонах коллекций) хеши для типов Date забиты жёстким образом, для чисел - тривиальные формулы умножения на хорошее иррациональное число "по модулю" разрядной сетки типа. И стратегия зашита "типовая". Т.е. подходящая для большинства случаев.
...
Рейтинг: 0 / 0
23.09.2009, 21:56:13
| Ответить | Цитировать | Написать  
Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
    #36213864
Фотография Василий Викторович
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Василий Викторович
Участник
MasterZiv
Василий Викторович wrote:

> при M искомых элеметов сложность вашего алгоритма равна O(N*M) что
> равноносильно (при M=N) O(N^2) + время вызовы функций

Василий Викторович, с тобой всё понятно. Ты просто не умеешь
считать O(). В приведённом mikhail_n алгоритме оно - O(N).
Т.е. линейное. Там как бы общего правила нет, и, конечно,
всё сложно, но конкретно в оценках операции сортировки
оценивают кол-во СРАВНЕНИЙ двух элементов.

иногда, например, для алгоритмов сортировки во внешней
памяти, оценивают кол-во ПЕРЕСТАНОВОК ЭЛЕМЕНТОВ, но
тогда это всегда оговаривается.

Так что и у тебя, в твоей формуле, видимо, должно быть
O(N) а не O(N**2).


согласен с замечанием
...
Рейтинг: 0 / 0
24.09.2009, 01:04:42
| Ответить | Цитировать | Написать  
25 сообщений из 29, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Можно ли создать структуру с временем поиска за O(N) и размером занимаемой памяти N
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36208911&tid=1344235]:
 0ms
get settings:
 11ms
get forum list:
 21ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 213ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 82ms
get tp. blocked users:
 1ms
others: 233ms
total:  585ms
созд. / загр.: 585ms
x
x
Закрыть


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