|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
16.08.2016, 18:35 | #1 |
Регистрация: 16.08.2016
Сообщений: 5
|
Оценка вычислительной сложности алгоритма [MatLab]
Всем привет! В общем вопрос может показаться легким, но к сожалению для меня он не так тривиален, как кажется. Собственно хотелось бы оценить вычислительную сложность алгоритма, но в силу моих скромных знаний (абсолютно "нулевых") не имею возможности верно провести оценку. Для справки: язык - MatLab.
PHP код:
|
16.08.2016, 19:33 | #2 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
Параметры NQ, Nel.
Берём самую операцию относительно какой будем считать. В данном случае умножение - T0. Код:
Код:
Тоже самое можно доказать другим путём. Вычитание вычитание относительно умножения по времени занимает с*T0 c некоторая константа, если умножение делают через сложение то с=1/64 на 64 битном компьютере. Мы можем заменить оценкой сверху T0. 2) Код:
Итого имеем 4-операции выполняемые отсюда время выполнение T1=4*T0 По свойствам O() константа убирается. O(1) для данной строчке. O2(1) <=> 4*T0 3) Код:
4) Код:
O4(Nel) <=> Nel*T4; 5) Код:
T5_1=2*Nel^2*T0 Умножение вектора на вектор операция линейная. T5_2=2*Nel*T0 T5=T5_1+T5_2 Оценка сверху для T5_1 всегда больше T5_2б поэтому можем сделать замену оценкой сверху. T5Up=T5_1+T5_1=2*T5_1=4*Nel^2*T0 Константа по правилам O() убирается O5(Nel^2)<=>4*Nel^2*T0 6) Чуть не пропустил строчку. Код:
"-pi/2" - константа pi/NQ - выполняется за c1*T0 -pi/2+ pi/NQ*m2 - выполняется за c2*T0 T6=c1*T0+T0+C2*T0=(1+c1+c2)*T0 По правилам O() если время не зависит от параметра то O ()- константан O6(1) 7) Код:
По правилам O() заменяем наибольшей степенью. O7(?)=NQ*O(Nel^2) Отсюда O7(NQ*Nel^2) Ответ сложность алгоритма O(NQ*Nel^2).
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
17.08.2016, 17:23 | #3 |
Регистрация: 16.08.2016
Сообщений: 5
|
Спасибо за ответ! Подскажи, если руководствоваться мыслями из данной статьи, то ответ будет O(NQ*Nel). В чем я ошибаюсь?
https://habrahabr.ru/post/104219/ |
17.08.2016, 17:47 | #4 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
В данном коде по знаком '*' и ' прячется вызов функций. Вы этого не учли.
Скорость исполнения определяет самая медленная функция/операция. А в матлабе операторы имеют асимтотическую сложность, а не постоянную.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . Последний раз редактировалось Pavia; 17.08.2016 в 17:50. |
18.08.2016, 07:01 | #5 |
Регистрация: 16.08.2016
Сообщений: 5
|
Еще раз спасибо! Не могли бы вы проверить мои мысли, относительно другого алгоритма?
Код:
Код:
2) (V1*En)*En' - опять же получается умножение вектора на матрицу, т.е. O(Nel^2) (входе умножения получается вектор); 3) [(V1*En)*En']*V - умножение вектора на вектор, т.е. O(2*Nel). Итого: O(Nel^2+Nel^2+2*Nel)*O(NQ)=O(NQ*Nel ^2), верно? |
18.08.2016, 07:43 | #6 |
Лис
Старожил
Регистрация: 18.09.2015
Сообщений: 2,409
|
Да верно. Только забыли шрих, транспонирование матрицы En.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал . |
23.08.2016, 08:34 | #7 |
Регистрация: 16.08.2016
Сообщений: 5
|
Спасибо!
|
08.02.2020, 13:16 | #8 |
Новичок
Джуниор
Регистрация: 08.02.2020
Сообщений: 2
|
Всем добрый день!
Вопрос по теме. Хотел бы сам научиться определять вычислительную сложность алгоритма. Это нужно для моей научной работы в области радиосвязи. Но из приведенного выше примера пока еще не все понял, так как в изложенном коде были перечислены не все математические операции. Имею код в MATLAB: Код:
Операция norm(Y,'fro') - норма Фробениуса, которая означает корень из суммы квадратов модулей каждого из элементов матрицы. constel_diff(:,:,m) - таких матриц определенное количество m, каждая из которых подставляется в выражение. В итоге получаем строку из значений d(:,m), которая нужна для дальнейших расчетов. Последний раз редактировалось mike84; 08.02.2020 в 13:26. |
08.02.2020, 16:07 | #9 |
Новичок
Джуниор
Регистрация: 08.02.2020
Сообщений: 2
|
Да, и вопрос, как относится к действиям: деление, комплексное сопряжение, модуль, сравнение, возведение в степень? Потому как в сети полно только простых примеров с квадратными уравнениями.
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
C++ Сложности построения алгоритма | laFleuere | Помощь студентам | 0 | 23.02.2014 23:45 |
Оценка вычислительной сложности элементарного алгоритма | TokSeven | Свободное общение | 4 | 29.01.2014 11:53 |
Оценка времени работы алгоритма | Utkin | Общие вопросы по программированию, компьютерный форум | 5 | 25.09.2013 13:11 |
Оценка сложности алгоритмов | Kristen_McBrian | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 22.12.2010 02:09 |
Оценка алгоритма | Алежа | Помощь студентам | 7 | 20.01.2009 14:28 |