Что этот график говорит о временной сложности?

------ Y---X
0,035 1000
0,089 2000
0,183 3000
0,315 4000
0,502 5000
0,693 6000
0,925 7000
1,222 8000
1,630 9000
1,998 10000
2,234 11000
2,651 12000
3,0 96 +13000
3,667 14000
4,328 15000
4,865 16000
5,496 17000
6,288 18000
7,037 19000
8,036 20000
19,032 30000
34,167 40000
54,505 50000Что этот график говорит о временной сложности?

Y здесь соответствует нет. случайных элементов, принятых в качестве входных данных, и X вычисляется с использованием функции времени в C++ (time.h)

Я хочу знать, что вы можете извлечь из этого графика о временной сложности моего алгоритма сортировки?

Этот график имеет время (в секундах) на оси X и нет. элементов на Y-Axix: http://tinypic.com/r/24cz600/8 Пожалуйста, нажмите на ссылку

источник

2015-05-05 Anand Akshay

График является логическим или sqrt-подобным. Но было бы сложно сказать что-то о функции. Вы можете попробовать ручной подгонку точки – ColOfAbRiX

Есть ли способ узнать о возможной функции с помощью какой-либо техники? –

Построение N по оси x будет более логичным, и вы увидите, что диаграмма выглядит как степенной закон. Построение точек на логарифмических осях было бы еще лучше, и было бы проще оценить мощность, на которую должен быть поднят N. – atkins

Это говорит о том, что сложность почти определенно O (N^2) (потому что она работает слишком долго). В соответствии с этим вы можете сделать некоторые предложения по самому алгоритму сортировки - например, это может быть сортировка пузырьков.

источник

2015-05-05 16:23:31

Это определенно не n^2 ... график не растет, он асимптотически приближается к фиксированному значению (кажется). Так что это скорее logX (n) ... Я дурак, который не умеет читать графики. – RedX

@RedX это n^2. Время должно быть на оси Y, а не на оси X. – dwcanillas

@ dwcanillas Вы совершенно правы. Извините за недосмотр :( – RedX

Ваш большой O почти наверняка n^2. Время должно быть на оси Y, так как это функция от n операций.

enter image description here

Как вы можете видеть на графике, есть вполне определенный, почти идеально подходят для п^2.

источник

2015-05-05 16:29:31 dwcanillas

http://mycurvefit.com/share/f318ddf8-3fb7-40e1-b773-bd7fc9bf87f3 придумали те же цифры. –

Не могли бы вы объяснить это немного больше? Почему это почти наверняка n^2? Спасибо заранее. – Tijme

@ 3ISvZFqczFBVUtz Подгонка к его данным имеет вид ax^2 + bx + c, с очень сильным коэффициентом корреляции. При определении Big O важны только самые большие темпы роста, которые будут x^2. [Этот пример] (https://en.wikipedia.org/wiki/Big_O_notation#Example) объясняет это очень хорошо. – dwcanillas

Что этот график говорит о временной сложности?

ответ

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