Помогите найти сложность алгоритма

gaal · Сообщение **gaal** » 28 июн 2009, 15:01

Привет!

B программе для дипломной работы находится прямая по массиву заданых точек при помощи метода наименьших квадратов.
Формула для нахождения параметров линейной функции использует следующий компонент:

$\frac {\sum_{i=1}^{n}{x_i}*{y_i} - \sum_{i=1}^{n}{x_i}*\sum_{i=1}^{n}{y_i}} {\sum_{i=1}^{n}{x_i}^2 - (\sum_{i=1}^{n}{x_i})^2}$

пол-дня, не могу понять, как найти сложность. Меня интересует верхняя граница, чаще всего для этого используется асимптотический анализ.

Помогите, кто знает
Спасибо

qwertylol · Сообщение **qwertylol** » 28 июн 2009, 15:19

gaal писал(а):Source of the post
пол-дня, не могу понять, как найти сложность.

Что такое "сложность"? Тут можно десяток подходящих определений придумать.

gaal · Сообщение **gaal** » 28 июн 2009, 15:41

qwertylol писал(а):Source of the post
gaal писал(а):Source of the post
пол-дня, не могу понять, как найти сложность.

Что такое "сложность"? Тут можно десяток подходящих определений придумать.

придумать я тоже многое могу, мне по существу ответ нужен.

Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.

Никакие другие значения лично мне не известны.

qwertylol · Сообщение **qwertylol** » 28 июн 2009, 16:02

gaal писал(а):Source of the post
придумать я тоже многое могу, мне по существу ответ нужен.

Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.

Никакие другие значения лично мне не известны.

Это и есть по существу. См. Седжвика "Фундаментальные алгоритмы на C++", часть 1, глава 2. Привлекать математику тут совсем необязательно, достаточно проверить экспериментально и посмотреть к чему ближе.

gaal · Сообщение **gaal** » 28 июн 2009, 16:09

qwertylol писал(а):Source of the post
gaal писал(а):Source of the post
придумать я тоже многое могу, мне по существу ответ нужен.

Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.

Никакие другие значения лично мне не известны.

Это и есть по существу. См. Седжвика "Фундаментальные алгоритмы на C++", часть 1, глава 2. Привлекать математику тут совсем необязательно, достаточно проверить экспериментально и посмотреть к чему ближе.

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

Таланов

gaal писал(а):Source of the post
Значит так: "сложность алгоритма" - выражение из теории алгоритмов, означает оценку времени выполнения программы. Чаще всего необходимо найти верхнюю границу при помощи асимптотического анализа, то есть при количестве входных данных стремящемся к бесконечности.

Никакие другие значения лично мне не известны.

Верхней границы значит не существует. Есть понятие линейной сложности. $$T=kN$$

. Проверьте на линейность, может подойдет.

Pyotr · Сообщение **Pyotr** » 28 июн 2009, 16:20

Достаточно очевидно, по-моему, что трудоемкость алгоритма растет линейно c $$n$$

.

qwertylol · Сообщение **qwertylol** » 28 июн 2009, 16:30

gaal писал(а):Source of the post
B том то и дело, что кроме результатов тестов нужно теоретическое обоснование, т.к. дипломная это.

Чтоб проводить асимптотику, нужно иметь функцию от времени. Тут можно посчитать только количество различных математических операций, если считать, что все они выполняются за одинаковое время и время больше ни на что не тратится, то получится 7n+5.

Hottabych · Сообщение **Hottabych** » 28 июн 2009, 16:31

насколько я понимаю, нужно сначала просто подсчитать количеству умножений и сложений

gaal · Сообщение **gaal** » 28 июн 2009, 16:38

Pyotr писал(а):Source of the post
Достаточно очевидно, по-моему, что трудоемкость алгоритма растет линейно c .

Спасибо за скорый ответ

He совсем понял, в силу чего очевидна линейная трудоемкость?:acute:
B знаменателе присутсвуют квадраты, кроме того в числителе перемножаются x и y под знаком суммы, или их суммы. Чисто интуитивно я бы сказал, что верхняя граница O(n^2).
Собственноо моя трудность в том, что я не знаю, как искать предел приведеной функции. Мне кажется, если разобраться c этим, то остальное - "дело техники".

Маленькое добавление: предел при n стремящемся к бесконечности.

yourdomain.com