Вычисление времени выполнения и пространства программы - PullRequest
2 голосов
/ 08 января 2012

Есть ли хорошее руководство, чтобы понять, как рассчитать время выполнения и пространство для данного фрагмента кода?Я смотрю на эти книги по кодированию, и вопросы показывают время выполнения, но нет никакого объяснения того, как это получается.Я знаю основную концепцию Big Oh, но есть ли какие-то основные правила или приемы для определения требований к памяти и пространству?

Возможно, я не смотрю в нужном месте, но любая помощь или ссылка на какое-нибудь полезное руководство было бы здорово!

Спасибо

Ответы [ 5 ]

3 голосов
/ 08 января 2012

Get Введение в алгоритмы .Это все там.

Они также подготовили видео-лекции интересующей вас части: http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/ Прокрутите вниз для видео.

2 голосов
/ 08 января 2012

Также: попробуйте курс Стэнфорда CS106B. Вы можете бесплатно скачать записи лекций с iTunes U. Настоятельно рекомендуется:)

http://see.stanford.edu/see/courseinfo.aspx?coll=11f4f422-5670-4b4c-889c-008262e09e4e

1 голос
/ 08 января 2012

Основные правила: каждая операция занимает 1;Вы пытаетесь понять, сколько раз вы делаете что-нибудь.То есть цикл будет занимать ровно количество итераций, умноженное на стоимость его тела.

Память еще проще: когда вы создаете структуры, следите за распределением.Плюс каждый рекурсивный вызов стоит вам всех локальных переменных.Вот и все.Легко, да?

Что касается онлайн-ресурсов, попробуйте http://www.cs.sunysb.edu/~algorith/video-lectures/ - вас больше всего заинтересует часть 2, Асимптотическая нотация.

Кроме того, самое время зарегистрироваться наhttp://www.cs101 -class.org / и http://www.algo -class.org / занятия в Стэнфорде, бесплатные и в точку.

0 голосов
/ 08 января 2012

Почему бы не прочитать некоторые книги, такие как MIT "Введение в алгоритмы 2", Sanjoy Dasgupta "Algorithms" или Sedgewick "Algorithms in C"?

0 голосов
/ 08 января 2012

Большой O дает представление о том, как масштабируются требования к времени и памяти на идеальной машине.Ресурсы, необходимые на реальном компьютере для скромных объемов данных, лучше всего измерять с помощью профилировщика.

...