Определение времени и пространства программы

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

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

Благодаря

источник

2012-01-08 user807496

https://en.wikipedia.org/wiki/Introduction_to_Algorithms –

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

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

источник

2012-01-08 13:09:28

Получить Introduction to Algorithms. Это все.

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

источник

2012-01-08 13:01:16 Tudor

Я бы это сделал, но любые хорошие ссылки для изучения материала в Интернете? – user807496

Добавлена ссылка с видео-лекциями из книги. – Tudor

Cormen & Co далеки от того, чтобы быть «учебником», я боюсь: технически это действительно так, это не простой способ понять концепции. Лекена более практична; достаточно смешно, даже в SICP понятие времени и пространства дается очень графически и, следовательно, легче понять. – alf

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

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

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

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

источник

2012-01-08 13:07:46 alf

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

источник

2012-01-08 13:26:30

это так не так по-разному ... Профайлер действительно хорош, и не имеет никакого ниспровержения, но ... – alf

Например, разница между O (n^2) и O (n ln n) не является чем-то необходимым профилировщик. С другой стороны, работа над алгоритмической сложностью для нематериальной части - пустая трата времени. Все это не имеет ничего общего с идеальной машиной, нет «лучшего»: это два разных инструмента для двух совершенно разных задач. – alf

Вы можете посмотреть на O (n^2) и O (n ln n), но это не дает вам никаких представлений о факторах и мало указывает на то, как он ведет себя на реальной машине для скромного/реалистичного размера данных. Если у вас есть один алгоритм, который занимает в два раза больше другого, вы не будете знать, что является первым и вторым. –

Почему бы не прочитать некоторые книги, как «Введение в алгоритмы 2» MIT, «Алгоритмы» Санджоя Дасгупты или «Алгоритмы» Седжуика в C?

источник

2012-01-08 14:06:36

Определение времени и пространства программы

ответ

Смежные вопросы