Анализ алгоритмов - ожидаемые темпы роста

У меня вопрос о разъяснении моей домашней работы.Анализ алгоритмов - ожидаемые темпы роста

http://www.cs.bilkent.edu.tr/~gunduz/teaching/cs201/cs201_homework3.pdf

Чтобы увидеть раздаточный материал, пожалуйста, перейдите на страницу 25 http://www.scribd.com/nanny24/d/36657378-Data-Structures-and-Algorithm-Analysis-in-C-Weiss.

Следующее - это то, что мне нужно сделать, но я не понял, что это значит. Означает ли это, что для алгоритма 1 сопоставить фактическое время работы по сравнению с (n^3 + 3 * (n^2) + 2 * n)/6, n = размер массива? Я так не думаю, но я ничего не мог сделать. Не могли бы вы объяснить мне, что это?

2- Plot the expected growth rates obtained from the theoretical analysis (as given for each solution) by 
using the same N values that you used in obtaining your results. Compare the expected growth rates 
and the obtained results, and discuss your observations in a paragraph.

EDIT 2:

Algorithm 1: 
    n   actual running time(ms)  (n^3 + 3*(n^2) + 2*n)/6 (I don't know whether the type is millisecond or not) 
    100   1      171700 
    1000  851      167167000

Так, учитывая эту огромную разницу между фактическим временем работы и теоретического времени работы, какие средства инструктор может отличаться теоретической функции времени сложность, которая является (п^3 + 3 * (n^2) + 2 * n)/6 для алгоритма 1. Это функция: http://www.diigo.com/item/image/2lxmz/m7y3?size=o

источник

2012-04-21 Anonymous

Что? Этот результат неплохо подходит для кубического роста. Попробуйте запустить его для 'n = 2000' и' n = 5000', чтобы получить больше точек данных. –

Не должно ли 167167000 быть ближе к 851? –

Вы не должны сравнивать два набора по их абсолютным значениям, попробуйте нормализовать наблюдаемый набор, разделив все записи на 171700, а затем сравните. – enobayram

Да, ваш инструктор означает «ожидаемый темп роста» прогнозируемое время работы после того, как вы включите значение от n в теоретической временной сложности.

Хотя это стандартное использование, я бы по-прежнему проконсультировался с инструктором, если бы был вами.

источник

2012-04-21 18:47:25 rrufai

Можете ли вы проверить последнее добавление, которое я только что написал выше? Разница между фактическим временем работы и теоретическим временем работы ОЧЕНЬ огромна. Поэтому, учитывая эту огромную разницу, то, что означает инструктор, может отличаться от теоретической функции временной сложности, которая является (n^3 + 3 * (n^2) + 2 * n)/6 для алгоритма 1. Это функция: http : //www.diigo.com/item/image/2lxmz/m7y3? size = o –

@noarm Весы разные. Важно то, что две функции имеют одинаковую форму. Предположим, вы повышаете скорость выполнения, умножая все на 20,0000, число начинает выглядеть примерно одинаково. Это точка эксперимента. Чтобы продемонстрировать, что фактическое время выполнения имеет отношение к теоретическим оценкам, игнорируя коэффициенты умножения. Это немного ясно? – rrufai

Да, спасибо. –

Теоретическое число, вероятно, количество операций или сравнений или что-то подобное.

Я полагаю, что темп роста означает , как быстро это значение растет?. Когда n идет от 100 до 1000, теоретическое значение увеличивается на коэффициент 167167000/171700 = 973.6 по сравнению с измеренным коэффициентом действительного значения 851.

источник

2012-04-21 20:40:14 WolframH

Анализ алгоритмов - ожидаемые темпы роста

ответ

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