Работа со временем и памятью: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 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