@nikitosis

Как узнать приблизительную сложность алгоритма, зная время его выполнения?

Есть функция f(x)=y, где x-кол-во элементов, которые принимает алгоритм, y- время выполнения алгоритма.
Имея несколько таких точек (x,y) нужно приблизительно определить сложность алгоритма.
Другими словами, имея эти точки на графике, нужно среди таких функций как {n,n^2,nlogn,n!,...} определить такую, которая будет наиболее приближенной к данным точкам.
  • Вопрос задан
  • 257 просмотров
Пригласить эксперта
Ответы на вопрос 3
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Модульная разность отношений Y к известному перечню сложностей {n,n^2,nlogn,n!,...}.
Ближайшая дробь, стремящаяся к единице, И одна из их взаимных разностей (расстояний) - стремящихся к нулю, и будет искомое значение.
Ответ написан
Абстрагируясь от алгоритмов и их сложности в Big-O-нотации, задача сводится к подсчёту различий значений данной функции и функций-кандидатов на каком-то множестве контрольных точек.

Взять какой-то набор значений [x0, x1, ... xN].
Получить «правильные» y_true = [f(x0), f(x1), ... f(xN)]
Для каждой функции-кандидата из этих же x получить их «предсказания» y_pred = [Fn(x0), Fn(x1), ... Fn(xN)]

Определить, какая из функций меньше всего «ошиблась». Для этого сложить квадраты разниц y_true - y_pred выданных каждой из функций на наборе входных значений x

Наименьшая сумма укажет наиболее вероятного кандидата.

Например,
x = [1, 2, 4, 8, 16, 32, 64]
f(x) = [y0, y1, y2, y3, y4, y5, y6]

// n
[1, 2, 4, 8, 16, 32, 64]
sum = (y0 - 1)^2 + (y1 - 2)^2 + (y2 - 4)^2 + ... + (y6 - 64)^2 = sum0

// n^2
[1, 4, 16, 64, 256, 1024, 4096]
sum =  (y0 - 1)^2 + (y1 - 4)^2 + (y2 - 16)^2 + ... + (y6 - 4096)^2 = sum1

// так же посчитать суммы ошибок для остальных функций:
// n * log(n),  n!


минимальное значение среди sumN укажет функцию, наиболее близкую к искомой.
Ответ написан
mindtester
@mindtester
учусь не реагировать на вопросы.. пока трудно.. ))
ну блин..
Оценка сложности алгоритмов
.. и вообще
Как узнать приблизительную сложность алгоритма, зная время его выполнения?
&&
Есть функция f(x)=y, где x-кол-во элементов, которые принимает алгоритм, y- время выполнения алгоритма.
Имея несколько таких точек (x,y) нужно приблизительно определить сложность алгоритма.
Другими словами, имея эти точки на графике, нужно среди таких функций как {n,n^2,nlogn,n!,...} определить такую, которая будет наиболее приближенной к данным точкам.
вторая часть это вообще то апроксимация.. вы ее решили?
это опорная точка. без нее - весь вопрос фуфло
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы