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

Материал из Algocode wiki
Версия от 11:22, 13 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «На олимпиадах вам часто требуется решить : зайдет ли ваша программа по памяти или по врем...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

У каждой задачи есть свои ограничения, стандартное : 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