Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
1

Сложность алгоритма

25.05.2011, 19:29. Просмотров 1977. Ответов 12
Метки нет (Все метки)

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

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
Program Spline;
uses crt,dos;
type vector=array [0..1000] of real;
var x,y,c:vector;
    x0,x9,h,x1,p,p1,p2,e:real;
    n,i:integer;
    hour,min,sec,hund:word;
    t,t1,t2:longint;
 
function f(x:real):real;
begin
 f:=sqr(sqr(x))-5*sqr(x)-x+1;//исходная функция
end;
 
{Вычисление коээфициентов сплайна}
procedure Coeff(n:integer; var x,f,c:vector);
var i,j,m:integer;
    a,b,r:real;
    k:vector;
begin
 {Прямой ход прогонки}
 k[1]:=0; c[1]:=0;
 for i:=2 to n do begin
  j:=i-1;
  m:=j-1;
  a:=x[i]-x[j];
  b:=x[j]-x[m];
  r:=2*(a+b)-b*c[j];
  c[i]:=a/r;
  k[i]:=(3.0*((f[i]-f[j])/a-(f[j]-f[m])/b)-b*k[j])/r;
 end;
 {Обратный ход прогонки}
 c[n]:=k[n];
 for i:=n-1 downto 2 do c[i]:=k[i]-c[i]*c[i+1];
end;
 
procedure Spl (n:integer; var x,f,c:vector; x1:real; var p,p1,p2:real);
{Построение сплайна. x,f - исходные данные, c - вектор коэффициентов,
наденный процедурой Coeff, x1 - значение x, для которого строим сплайн,
p - значение сплайна в точке, p1,p2 - 1-я и 2-я производные}
var i,j:integer;
    a,b,d,q,r:real;
begin
 i:=1;
 while (x1>x[i]) and (i<>n) do i:=i+1; {Ищем номер соседнего узла}
 {Промежуточные переменные и коэффициенты}
 j:=i-1; a:=f[j]; b:=x[j]; q:=x[i]-b;
 r:=x1-b; p:=c[i]; d:=c[i+1];
 b:=(f[i]-a)/q - (d+2*p)*q/3.0;
 d:=(d-p)/q*r;
 {Считаем значения сплайна и его производных:}
 p1:=b+r*(2*p+d);
 p2:=2*(p+d);
 p:=a+r*(b+r*(p+d/3.0))
end;
 
begin
 clrscr;
 writeln('Построение кубического интерполяционного сплайна');
 writeln('Функция Y(x)=x^4+5x^2-x+1');
 writeln('Введите границы по оси X для построения сплайна:');
 read(x0,x9);
 writeln('Введите шаг по X для построения значений сплайна:');
 read(h);
 n:=round((x9-x0)/h);
 x[0]:=x0; y[0]:=f(x0);
 {Вычисление значения функции}
 for i:=1 to n do begin
  x[i]:=x[i-1]+h;
  y[i]:=f(x[i]);
 end;
 writeln ('Значение X':19,'Функция':19,'Сплайн':19,'Отн.ошибка':19);
 {расчёт выполнения интерполяции}
 GetTime(hour,min,sec,hund);
 t1:=sec*1000+min*60000+hund*10;{переведем в миллисекунды}
 {Нахождение коэффициентов C с помощью прогонки}
 Coeff (n,x,y,c);
 {Нахождение сплайнов и расчёт ошибки}
 for i:=0 to n do begin
  Spl(n,x,y,c,x[i],p,p1,p2);
  e:=abs(y[i]-p)/abs(y[i]);
  writeln(x[i]:19:8,y[i]:19:8,p:19:8,e:19:8);
 end;
 GetTime(hour,min,sec,hund);
 t2:=sec*1000+min*60000+hund*10;
 t:=t2-t1;
 writeln('Время расчёта сплайнов в миллисекундах: ',t);
 readkey;
end.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2011, 19:29
Ответы с готовыми решениями:

Сложность Алгоритма
народ подскажите пожалуйста как посчитать сложность вот такого кода (или хотя бы литературу...

сложность алгоритма
подскажите, как росчитать сложность алгоритма. в том числе алгоритм сортиро́вки пузырько́м :...

Сложность Алгоритма
Помогите пожалуйста разобраться. Я не прошу за меня решать!!!! В данной задаче нужно заполнить...

Сложность алгоритма
Кто бы объяснил рабоче-крестьянским языком что такое O(N) ? И если есть сложность алгоритма O(N +...

Сложность алгоритма
пусть имеется алгоритм f со сложностью О(n*log n). Если этот алгоритм запускается в цикле n раз ...

12
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.05.2011, 19:34 2
Что-то вроде О(C*N)
0
Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
25.05.2011, 19:40  [ТС] 3
А что такое С???

Я нашел какое-то обьяснение по этой теме только вот не знаю сложность так как там рассчитывать нужно???
Если кому не сложно посмотрите пожалуйста.
Ссылка
0
silent_1991
Эксперт С++
5013 / 3073 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
25.05.2011, 19:45 4
Нет, беглым взглядом глянул, вроде O(N^2), поскольку в главном цикле вызывается функция Spl, в которой тоже есть цикл до n (в общем случае).
0
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.05.2011, 19:57 5
Predvestnik, принято считать С - некоторой константой, не зависящей от входных данных. Вообще идейно оценка сложности алгоритма - зависимость времени исполнения программы от входных данных. Единичная сложность - время работы не зависит от входных данных, например
Pascal
1
2
3
4
5
var a, b: longint;
begin
readln(a);
for a := 1 to 1000 do b := a;
end.
Тут какое а не введете, время выполнения будет одинаковым.
Тут же вводится понятие элементарного действия - например, арифметическое действие, занесение значения в память, его чтение.
Так вот, при оценке сложности алгоритма рассчитывается функция, которая вернет примерное колличество элементарных операций, которое будет выполнено при конкретном наборе входных данных.

Добавлено через 2 минуты
silent_1991, там же инкремент n - i раз, мне кажется, даже при самых больших n - i это будет незаметно
0
Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
25.05.2011, 19:58  [ТС] 6
Цитата Сообщение от silent_1991 Посмотреть сообщение
Нет, беглым взглядом глянул, вроде O(N^2), поскольку в главном цикле вызывается функция Spl, в которой тоже есть цикл до n (в общем случае).
А в процедуре Coeff тоже есть цикл до n, он не будет влиять???
0
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.05.2011, 20:00 7
Цитата Сообщение от Predvestnik Посмотреть сообщение
А в процедуре Coeff тоже есть цикл до n, он не будет влиять???
Coeff вызывается только один раз, из-за чего и константа
0
silent_1991
Эксперт С++
5013 / 3073 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
25.05.2011, 20:04 8
Цитата Сообщение от iama Посмотреть сообщение
там же инкремент n - i раз
Не совсем понял, почему? Может получиться так (в алгоритме не разбирался, чисто предположение), что мы постоянно будем попадать на конец массива, и i всегда будет приближаться к n.

Не по теме:

Вообще в коде сложновато ориентироваться, несколько инструкций в строке - зло))

0
Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
25.05.2011, 20:08  [ТС] 9
Исправьте меня пожалуйста если я ошибаюсь:
все действия такие как вывод на экран, вызов процедуры, присваивание, которое происходит один раз мы принимаем за константу и не берём во внимание, там где используются циклы такие как for i:=1 to n сложность= О(n) и степень n увеличивается в зависимости от того присутствуют ли подциклы.
0
iama
1329 / 980 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.05.2011, 20:12 10
silent_1991, действительно, в худшем случае в этой подпрограмме (вызываемой N раз) тоже будем иметь N, но я имел в виду, что 32000 раз выполнить инкремент переменной - это почти не скажется на скорости работы программы, хотя на слабых машина, кто знает... В целом и получается примерно от О(C*N), причем С довольно большое, до квадрата.

Добавлено через 38 секунд
Predvestnik, ну как бы да. Это может быть не только N, могут быть другие вводимые данные, притом при расчете берем только самую большую степень, остальные часто отбрасывают, так так при больших ограничениях они не будут играть такой роли
0
Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
25.05.2011, 20:31  [ТС] 11
в основной программе два цикла for i:=1 to n это показывает С???

ну а допустим если убрать процедуры и оформить как одну программу тогда выйдет что в цикле for i:=1 to n будет присутствовать while (x1>x[i]) and (i<>n), это не отразиться на сложности???
0
silent_1991
Эксперт С++
5013 / 3073 / 271
Регистрация: 11.11.2009
Сообщений: 7,045
Завершенные тесты: 1
25.05.2011, 21:16 12
Сложность - это не какая-то конкретная величина, это только общий закон, описывающий зависимость времени выполнения (возможно, числа операций) от входных данных. Поэтому не учитываются такие вещи, как константы, незначащие составляющие (скажем, на параболу не повлияет то, что мы к x^2 прибавим 3x и отнимем 5, а потом всё это на 3 умножим, она всё равно параболой останется), вызовы функций и так далее. Поэтому оформите вы всё в одной функции или нет - на сложность это не повлияет, иначе алгоритмы упрощались бы простой реорганизацией кода.
0
Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
25.05.2011, 21:55  [ТС] 13
ну впринципе понятно почему такая сложность выйдет...
0
25.05.2011, 21:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2011, 21:55

Сложность алгоритма
Есть псевдокод следующего алгоритма function search(k,m: int, x:double): bool; var l: int; ...

Сложность алгоритма
Здравствуйте. Подскажите, как можно определить сложность многократной рекурсии. Вот нашел...

Вычислительная сложность алгоритма
Пожалуйста, помогите. Нужна вычислительная сложность статистических методов кластерных анализов и...


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

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

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