Как формулы получены из этих строк кода? - PullRequest
2 голосов
/ 22 января 2012

Я перехожу к следующей книге - http://www.amazon.com/Algorithms-4th-Robert-Sedgewick/dp/032157351X, и в одном из разделов рассказывается о получении формул из кода для оценки производительности.

Например, формула строки D - "N 3 / 6 - N 2 / 2 + N / 3 ".Я вижу, что три "N" для трех для петель.И как куб и квадрат получены.Но почему «N 3 / 6» и почему вычитание, а затем сложение?

Performance Calculation

Спасибо.

Ответы [ 4 ]

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

Иногда это помогает конкретизировать числа и проследить всю программу (как бы), ставя конкретные числа для каждой из величин, которые вас смущают.

Так что в этом случае, если N (произвольно) 10, что происходит?

Что ж, для блока A это не имеет значения: это выполняется один раз.

Для блока B это имеет значение: i начинается с 0 и выполняется до и включая i = 9, в общей сложности 10 выполнений, но N равно 10.

Для блока C он получаетхитрость: когда i равен 0, j инициализируется в 1 и выполняется до и включая j = 9 для общего количества 9 выполнений.Затем в следующий раз, при i = 1, j инициализируется до 2 и выполняется 8 раз и т. Д. Всего получается 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 раз.Но это (N ^ 2-N) /2.

Блок D и E следуют одинаково.

Тем не менее, вам не нужно кропотливо пробираться через всепример, вот так.Два ответа выше моих являются совершенно правильными и краткими.Для таких маленьких петель я обычно думаю геометрически: блок B подобен разметке меток на линейке, которая измеряет длину.Блок C подобен разметке квадратов на сетке, сначала строке 9, затем строке 8 и т. Д. Это что-то вроде области измерения, и в этом случае область выглядит как треугольник, площадь которого пропорциональнадо N ^ 2.

Если моя геометрическая аналогия не работает для вас, это нормально.Сделайте достаточно, и вы, надеюсь, получите интуитивно понятную структуру.

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

Мы смотрим только на возможности, когда i

1 голос
/ 05 февраля 2013

Вы также можете получить частоту строки D , решив следующее суммирование:

enter image description here

Примените соответствующие формулы, перечисленные здесь (первые два раздела).

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

Поскольку предел цикла для цикла j получен из текущего значения i, а предел для цикла k получен из текущего значения j.Если вы отработаете все математические вычисления, вы получите такое выражение.

...