Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
Здравствуйте, гость ( Вход | Регистрация )
Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более |
ViGOur |
21.8.2010, 17:39
Сообщение
#1
|
Мастер Группа: Модератор Сообщений: 3296 Регистрация: 9.10.2007 Из: Москва Пользователь №: 4 Спасибо сказали: 231 раз(а) Репутация: 40 |
Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей? |
|
|
igor_bogomolov |
21.8.2010, 22:54
Сообщение
#2
|
Профессионал Группа: Сомодератор Сообщений: 1215 Регистрация: 22.3.2009 Из: Саратов Пользователь №: 630 Спасибо сказали: 235 раз(а) Репутация: 29 |
на самом деле у него на каждом шаге сложность O(n) where n = 100, так как он использует список. Это Qt. QList - это не двусвязный список, и доступ до элемента осуществляется за O(1). http://doc.crossplatform.ru/qt/4.6.x/conta...hmic-complexity |
|
|
Текстовая версия | Сейчас: 20.4.2024, 5:46 |