использование утилиты времени unix для поиска класса эквивалентности для быстрой сортировки

Question

Я использовал утилиту времени, чтобы вычислить время пользователя для алгоритма быстрой сортировки с входными данными 10000, 20000, ..., 60000 слов, и вот результаты, которые у меня есть

n( in thousands)   T(n)
1                  1.740
2                  3.7 
3                  5.83  
4                  7.93
5                  10.18  
6                  12.41

Что я хочувыяснить, является ли f (n) таким, что T (n) = theta (f (n)), т. е. мне нужно угадать f (n) таким, что T (n) / f (n) приближается к ненулевой константе.Я попробовал следующие функции f (n), но, кажется, ничто не генерирует константу

f(n) =n
f(n) = nlogn
f(n) = n+sqrt(n)
f(n) = n^2
f(n)=n + logn
f(n)=1/n

Из того, что я сделал вывод, T (n) имеет n в качестве нижней границы и n log n в качестве верхней границы.Поэтому мне нужна функция между этими двумя значениями.Пожалуйста помоги.

Answer 1

У вас есть много возможных вариантов там. Я хотел бы начать с подгонки ваших данных к каждому из шести уравнений и выяснить, насколько хорошо работает подгонка. Например, если вы попытаетесь представить результаты, вы сразу увидите, что они находятся почти на одной прямой. Использование любого графического программного обеспечения поможет вам увидеть это. В науке и математике это всегда хорошая идея: постройте ваши результаты!

Мне было лень, поэтому я использовал Excel для подгонки прямой линии к вашим данным и нашел уравнение:

T(n) = 2.1379n - 0.524

с R ² 0,9995. Даже Excel предоставит вам эти значения R ² , чтобы сказать, насколько хорошо подходит данные (вы хотите, чтобы R ² было как можно ближе к 1). Теперь этот результат довольно хороший, и вы могли бы на этом остановиться, но я подумал, что постараюсь привести ваши данные в соответствие с остальными уравнениями и посмотреть, что я получил. Я обнаружил, что лучше всего подходят ваши шесть функций:

T(n) = 0.0327n<sup>2</sup> + 1.911n + 0.219

с R ² лучше 0,999! Теперь это действительно хорошо подходит. Конечно, если вы хотите большей точности, вам, вероятно, стоит попробовать это в Igor (бесплатно) вместо Excel. Тем более что известно, что Excel дает отрицательные значения R ² .

Я хочу сказать, что вы должны всегда стараться изобразить свои результаты. Это так легко в эти дни. После этого, я думаю, что вы были слишком обеспокоены тем, чтобы заново изобрести колесо и получить их сами. Для этого существует множество программ.