Форум программистов, компьютерный форум CyberForum.ru

Сортировка списка - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Unsigned char to vector http://www.cyberforum.ru/cpp-beginners/thread1145956.html
{ vector<byte> resBuffer; unsigned char buffer; //string reply; //Receive a reply from the server if( recv(sock , buffer , sizeof(buffer) , 0) < 0) { puts("recv failed"); }
C++ Тип BOOL Что API функции возвращают в качестве TRUE? 1? Или любой не 0? http://www.cyberforum.ru/cpp-beginners/thread1145953.html
Время затраченное на выполнение любой операции C++
Доброго времени суток. Подскажите пожалуйста как мне получить время затраченное на вычисление, например на выполнение цикла?
C++ Как изменить мантиссу double?
Привет! Как изменить мантиссу числа типа double? Есть в c++ какая-нибудь встроенная функция?
C++ Разбиение числа на цифры http://www.cyberforum.ru/cpp-beginners/thread1145894.html
здравствуйте, подскажите есть ли функция, которая разбивает число на другие числа, которые его составляют? к примеру число 294 разбивается на 2, 9 и 4
C++ Извлечение информации из BMP файла Есть вот такое вот задание: 1. Разработать программу, результатом которой будет следующая информация о свойствах графического файла BMP - ширина изображения, в пикселях; - высота изображения, в пикселях; - глубина цвета; - размер изображения в байтах; - размер файла. 2. Зафиксировать: адреса (порядковые номера), шестнадцатеричные и десятеричные значения байтов, а также значения... подробнее

Показать сообщение отдельно
IrineK
Заблокирован
12.04.2014, 08:44     Сортировка списка
Сортировки дают кво операций ~ N2
Если у вас N = 108, то N2 = 1016
Комп способен на порядка 107 в секунду.
Значит, вам нужно 109 секунд = 32 года.

Добавлено через 10 минут
Кво операций при бинарном поиске по N элементам 1 + log2N
Искать будем по списку, т.е. среднее кво операций будет вполовину меньше.
Нужно расставить N элементов, т.е. общее кво операций
N(1 + log2N) / 2

При N = 108 М = 1 + 8*log210 = 1 + 8*3,3 = 28 операций
Поскольку, список нарастает от 1 до N, среднее кво операций равно половине этой величины, т.е. 14 операций на одну вставку.
Для N вставок: 14 * 108 операций
Комп справится за 140 с.
 
Текущее время: 16:09. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru