Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
pikelson
0 / 0 / 0
Регистрация: 20.05.2015
Сообщений: 31
1

Анализ сложности алгоритмов. О-символика

07.06.2016, 16:39. Просмотров 1186. Ответов 1
Метки нет (Все метки)

Помогите разобраться. Нашел функцию f(n) алгоритма, допустим, 5n2+3n+4. Как найти О большое знаю, берется высший порядок функции. В задании нужно найти о малое, тета, омега большое и омега малое. Как это сделать? Алгоритм простой.
Вот пример.
3. Пусть дан фрагмент программы:
Pascal
1
2
3
4
5
6
7
S:=0; 
For i:=1 to n*n do 
begin s:=s+A[4, 3, 2, 1];
For j:=1 to 2*i do 
begin s:=s+A[5, 6, 7, 8]; 
For k:=1 to n do s:=s+A[2, 3, 4, 5]; end; end;
For m:=1 to n do s:=s+A[1, 2, 3, 4];
Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки тета( f(N)), O(f(N)), Омега-большое( f(N)), o(f(N)), омега-малое( f(N)), где N – длина входа.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.06.2016, 16:39
Ответы с готовыми решениями:

Определение временной сложности алгоритма (О символика)
Procedure R(n, x : integer); Var i, j :integer; begin S:=0; For i:=1 to 2*n do if a > х...

О символика (определение временной сложности алгоритма)
S:=0; For i:=1 to n*2 do begin s:=s+A; For j:=1 to n - 2 do begin s:=s+A; For k:=1 to n-3 do...

Сравнительный анализ алгоритмов
Здравствуйте, уважаемые форумчане! Прошу помощи в решении следующих задач: Задача 1. Пусть...

Анализ нерекурсивных алгоритмов
Помогите, пожалуйста, с решением 5) Улучшите реализацию приведенного ниже алгоритма умножения...

Амортизационный анализ алгоритмов
Доброго времени, ув. форумчане! Не могли бы вы объяснить мне амортизационный анализ алгоритмов или...

1
regio1961
278 / 152 / 120
Регистрация: 06.06.2016
Сообщений: 362
08.06.2016, 16:46 2
Для ясности отформатируем код:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
S:=0; 
    For i:=1 to n*n do 
    begin 
    s:=s+A[4, 3, 2, 1];
        For j:=1 to 2*i do 
        begin 
        s:=s+A[5, 6, 7, 8]; 
            For k:=1 to n do 
            s:=s+A[2, 3, 4, 5];    // For k
        end;     // For j
    end;    // For i
    For m:=1 to n do 
    s:=s+A[1, 2, 3, 4];
Присваивания типа s := s+A имеют константную сложность, обозначим ее http://www.cyberforum.ru/cgi-bin/latex.cgi?C, тогда
http://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
 \sum_{i = 1}^{n^2} \left( C \sum_{j = 1}^{2i} \left( C \sum_{k = 1}^{n} C \right)  \right) \,+\,  \sum_{m = 1}^{n}C = \sum_{i = 1}^{n^2} \left( C \sum_{j = 1}^{2i} \left( C^2 \sum_{k = 1}^{n} 1 \right)  \right) \,+\,  C\sum_{m = 1}^{n}1 = C^3 \sum_{i = 1}^{n^2} 2i n \,+\, Cn = <br />
= 2C^3n \sum_{i = 1}^{n^2}i \,+\, Cn = 2C^3 n \,\frac{(n^2 \,-\, 1)n^2}{2} \,+\, Cn = O(n^5).<br />
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2016, 16:46

О-символика
Здравствуйте, помогите сделать пару заданий. Сам не смог разобраться. 1.Проверить утверждения с...

О-символика
Здравствуйте помогите пожалуйста... 1.Проверить утверждения с помощью определения: 1) 2^N =...

О-символика
Прохожу курс по алгоритмам! Задачки запрограммировал, осталась теория по вычислению сложности...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru