Работа со временем и памятью

Материал из Algocode wiki
Перейти к: навигация, поиск

На олимпиадах вам часто требуется решить : зайдет ли ваша программа по памяти или по времени. Мы уже рассказали про асимптотику, как же ей пользоваться?


У каждой задачи есть свои ограничения, стандартное : 1 секунда, 128Mb памяти.


Научимся работать с этим : Когда вы решаете задачу, удобно полагать, что вы можете делать $2 \cdot 10^8$ простых операций в секунду, если вы пишите на c++, но более правильных подход - честно заслать в систему программу, которая делает $10^8$ операций и посмотреть за сколько она будет работать.


С памятью сложнее. Каждый тип потребляет свое количество байт. Основные типы перечислены ниже :

1) bool - 1 байт

2) int - 4 байта

3) long long - 8 байт

4) double - 8 байт


Теперь давайте посмотрим на вашу программу. Допустим вы используете 3 переменные типа bool, 1 int и массив на 1000 long long. Тогда ваша программа использует - $1000 \cdot 8 + 3 + 4 = 8007$ байт, в 1 килобайте - 1024 байт, следовательно наша программа потребляет меньше 8 килобайт, в мегабайте также 1024 килобайт, следовательно наша программа потребляет гораздо меньше 1 мегабайта памяти и точно подходит под ограничения.




Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin