Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
 Аватар для Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192

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

25.05.2011, 19:29. Показов 2683. Ответов 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
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
25.05.2011, 19:29
Ответы с готовыми решениями:

Сложность алгоритма
пусть имеется алгоритм f со сложностью О(n*log n). Если этот алгоритм запускается в цикле n раз for(int i=0;i&lt;n;i++) { ...

сложность алгоритма
подскажите, как росчитать сложность алгоритма. в том числе алгоритм сортиро́вки пузырько́м : procedure sort_bulbaska(var A:mas); ...

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

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

Я нашел какое-то обьяснение по этой теме только вот не знаю сложность так как там рассчитывать нужно???
Если кому не сложно посмотрите пожалуйста.
Ссылка
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
25.05.2011, 19:45
Нет, беглым взглядом глянул, вроде O(N^2), поскольку в главном цикле вызывается функция Spl, в которой тоже есть цикл до n (в общем случае).
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.05.2011, 19:57
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  [ТС]
Цитата Сообщение от silent_1991 Посмотреть сообщение
Нет, беглым взглядом глянул, вроде O(N^2), поскольку в главном цикле вызывается функция Spl, в которой тоже есть цикл до n (в общем случае).
А в процедуре Coeff тоже есть цикл до n, он не будет влиять???
0
 Аватар для iama
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
25.05.2011, 20:00
Цитата Сообщение от Predvestnik Посмотреть сообщение
А в процедуре Coeff тоже есть цикл до n, он не будет влиять???
Coeff вызывается только один раз, из-за чего и константа
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
25.05.2011, 20:04
Цитата Сообщение от iama Посмотреть сообщение
там же инкремент n - i раз
Не совсем понял, почему? Может получиться так (в алгоритме не разбирался, чисто предположение), что мы постоянно будем попадать на конец массива, и i всегда будет приближаться к n.

Не по теме:

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

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

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

ну а допустим если убрать процедуры и оформить как одну программу тогда выйдет что в цикле for i:=1 to n будет присутствовать while (x1>x[i]) and (i<>n), это не отразиться на сложности???
0
Эксперт С++
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
25.05.2011, 21:16
Сложность - это не какая-то конкретная величина, это только общий закон, описывающий зависимость времени выполнения (возможно, числа операций) от входных данных. Поэтому не учитываются такие вещи, как константы, незначащие составляющие (скажем, на параболу не повлияет то, что мы к x^2 прибавим 3x и отнимем 5, а потом всё это на 3 умножим, она всё равно параболой останется), вызовы функций и так далее. Поэтому оформите вы всё в одной функции или нет - на сложность это не повлияет, иначе алгоритмы упрощались бы простой реорганизацией кода.
0
 Аватар для Predvestnik
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
25.05.2011, 21:55  [ТС]
ну впринципе понятно почему такая сложность выйдет...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.05.2011, 21:55
Помогаю со студенческими работами здесь

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

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

Сложность Алгоритма
народ подскажите пожалуйста как посчитать сложность вот такого кода (или хотя бы литературу подкинте) while i&lt;=length(s) do ...

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

Сложность рекурсивного алгоритма
Добрый день, никак не могу понять как высчитывать сложность алгоритмов с рекурсией. Буду очень благодарна если кто-нибудь поможет...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru