Работа со временем и памятью: различия между версиями
Глеб (обсуждение | вклад) |
Глеб (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
На олимпиадах вам часто требуется решить : зайдет ли ваша программа по памяти или по времени. Мы уже рассказали про асимптотику, как же ей пользоваться? | На олимпиадах вам часто требуется решить : зайдет ли ваша программа по памяти или по времени. Мы уже рассказали про асимптотику, как же ей пользоваться? | ||
− | |||
У каждой задачи есть свои ограничения, стандартное : 1 секунда, 128Mb памяти. | У каждой задачи есть свои ограничения, стандартное : 1 секунда, 128Mb памяти. | ||
+ | ==Время== | ||
Научимся работать с этим : Когда вы решаете задачу, удобно полагать, что вы можете делать $2 \cdot 10^8$ простых операций в секунду, если вы пишите на c++, но более правильных подход - честно заслать в систему программу, которая делает $10^8$ операций и посмотреть за сколько она будет работать. | Научимся работать с этим : Когда вы решаете задачу, удобно полагать, что вы можете делать $2 \cdot 10^8$ простых операций в секунду, если вы пишите на c++, но более правильных подход - честно заслать в систему программу, которая делает $10^8$ операций и посмотреть за сколько она будет работать. | ||
+ | ==Память== | ||
С памятью сложнее. Каждый тип потребляет свое количество байт. Основные типы перечислены ниже : | С памятью сложнее. Каждый тип потребляет свое количество байт. Основные типы перечислены ниже : | ||
Строка 17: | Строка 18: | ||
4) double - 8 байт | 4) double - 8 байт | ||
− | |||
Теперь давайте посмотрим на вашу программу. Допустим вы используете 3 переменные типа bool, 1 int и массив на 1000 long long. Тогда ваша программа использует - $1000 \cdot 8 + 3 + 4 = 8007$ байт, в 1 килобайте - 1024 байт, следовательно наша программа потребляет меньше 8 килобайт, в мегабайте также 1024 килобайт, следовательно наша программа потребляет гораздо меньше 1 мегабайта памяти и точно подходит под ограничения. | Теперь давайте посмотрим на вашу программу. Допустим вы используете 3 переменные типа bool, 1 int и массив на 1000 long long. Тогда ваша программа использует - $1000 \cdot 8 + 3 + 4 = 8007$ байт, в 1 килобайте - 1024 байт, следовательно наша программа потребляет меньше 8 килобайт, в мегабайте также 1024 килобайт, следовательно наша программа потребляет гораздо меньше 1 мегабайта памяти и точно подходит под ограничения. |
Версия 08:23, 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