Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более Опции

[Алексей1153]

1. rValue = ++n; - зачем в 2 строки делать?

моё мнение - именно в 2 строки лучше. Нагляднее, плюс исключена ошибка. А то, что постфикс у простого типа - так это оптимизатор исправит сам, зато так красивее для глаза )

[wiz29]

Как и обещал, код:

Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.

[ViGOur]

Объясни как. Можно использовать только два массива!

[wiz29]

Объясни как. Можно использовать только два массива!

Множитель 'M' берется из линейности поиска в массиве значений, если данный массив поддерживать в сортированном виде, то поиск будет обходится в O(log2(M)), соответственно, получим более выгодную оценку для поиска.

[cross]

Сложность приведенного алгоритма О(M*N), можно сделать быстрее за O(log2(M)*N), но он сложней в реализации.

Согласен (о чем и писал ранее в соседней теме про эту задачу). Единственный линейный алгоритм, который мне видится, это если значение элементов лежит в интервале от 0 до Х (где Х не велико и нам хватает памяти) заводим массив из Х элементов, в котором индекс - это величина элемента в исходном множестве, а значение - число появлений этого элемента в исходном множестве. За один проход пересчитываем все элементы и берем нужное количество минимальных.