7 / 7 / 2
Регистрация: 10.02.2017
Сообщений: 164
Записей в блоге: 1
1

Как вычислять сложность алгоритма, или найти асимптотическую сложность любой программки?

11.06.2017, 13:31. Показов 8777. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Например
Вычислить x^n по алгоритму быстрого возведения в степень

Добавлено через 43 секунды
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
var
 
  x, n, r: word;
 
 
begin
 
  readln(x, n);
 
  r := 1;
 
  while n <> 1 do begin
 
    if odd(n) then r := r * x;
 
    x := x * x;
 
    n := n div 2
 
  end;
 
  writeln(x * r)
 
end.
Добавлено через 1 минуту
Из анализа данного алгоритма известно, что его асимптотическая сложность порядка O(log2n).
Как найти данный логарифм.
Есть ли простой способ, как например перевод чисел из одной системы в другую, запомнил и используешь?

Добавлено через 1 минуту
А если такая программулина, нужно разобраться в данном вопросе, или я не прав насче , нужно осмыслить тему асимптотическая сложность алгоритмов.
Какая тут сложность?
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
const n=8;
type country=record
      name:string[30];
      population:longint;
      square:real;
     end;
var
  a:array[1..n] of country;
  s,r:string;
  i,j:integer;
  f:file of country;
begin
  assign(f,'country.dat');
  if not FileExists('country.dat') or (Uppercase(ReadlnChar('Файл country.dat уже существует! перезаписать (Y/N)?'))='Y') then begin
    Rewrite(f);
    writeln('Введите данные по странам:');
    for i:=1 to n do begin
      writeln('Запись #',i);
      a[i].name:=ReadlnString('Название страны:');
      a[i].population:=ReadlnInteger('Население:');
      a[i].square:=ReadlnReal('Занимаемая площадь:');
      write(f,a[i]);
    end;
  end  
  else begin 
    reset(f);
    for i:=1 to 8 do read(f,a[i]);
  end;
  close(f);
    for i:=1 to n-1 do
      for j:=i+1 to n do if a[i].name>a[j].name then Swap(a[i],a[j]);
  writeln('отсортированный список:');
  writeln(format('{0,-40}{1,20}(чел){2,20}(км^2)','Название страны','Население','Занимаемая площадь'));
  for i:=1 to n do writeln(format('{0,-40}{1,20:N}{2,20:F}',a[i].name,a[i].population,a[i].square));
  s:=ReadlnString('Введите название страны:');
  r:='';
  for i:=1 to n do 
    if UpperCase(s)=UpperCase(a[i].name) then r:=r+format('{0,-40}{1,20:N}{2,20:F}',a[i].name,a[i].population,a[i].square)+NewLine;
  if r='' then writeln('Страна "',s,'" не найдена') else writeln(r);
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.06.2017, 13:31
Ответы с готовыми решениями:

Определить тип сортировки и её асимптотическую сложность
Можете подсказать какая сортировка тут используется? и ее асимптотическую сложность &lt;html&gt; ...

Найти сложность алгоритма
Дан алгоритм поиска максимума: m:=a For i:=2 to to n do If m&lt;a then m:=a; Понятно что...

Найти временную и емкостную сложность алгоритма
Необходимо найти временную и емкостную сложность алгоритма. Читал на википедии, другие источники,...

Как расчитывать сложность алгоритма
Читал на эту тему ,но всё-равно не могу сам определить сложность любого алгоритма.. когда цикл в...

1
Модератор
9956 / 5313 / 3327
Регистрация: 17.08.2012
Сообщений: 16,219
13.06.2017, 16:55 2
HaydoSpeed, можете считать, что O(что-то там) - это количество итераций цикла, необходимое для окончания вычислений при наихудшем случае (максимальное количество итераций). При этом берите в расчёт только целевую часть алгоритма, а не программу в целом.

При быстром возведении в степень число n делится на два до тех пор, пока не станет равным 1. найдём количество итераций k, необходимых для этого. Каждую итерацию n делится на 2, при последней итерации n будет разделено на 2k, то есть:

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
\frac{n}{2^k}=1<br />

Находим это самое k, и дело в шляпе.

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
\frac{n}{2^k}=1\ \Rightarrow \ 2^k=n\ \Rightarrow \ k=\log _2n<br />

Количество итераций - это и есть сложность алгоритма, то есть, можно записать, что сложность алгоритма быстрого возведения в степень есть O(log2n).

Теперь оценим сложность алгоритма для второй программы. Не принимаем во внимание ввод-вывод и прочую подготовку данных. Целевым алгоритмом в данном случае можно считать сортировку выбором, то есть, строки 30 и 31. Очевидно, что количество итераций будет

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
k=\sum_{i=1}^{n-1}(i+1)=2+3+...+n=\frac{(n+2)(n-1)}{2}<br />

Можно, конечно, абсолютно точно записать, что сложность сортировки будет

https://www.cyberforum.ru/cgi-bin/latex.cgi?<br />
O\left( \frac{(n+2)(n-1)}{2}\right)<br />

Однако, при асимптотическом анализе алгоритмов считается, что n → ∞, а постоянные множители не учитываются. Поэтому выбрасываем слагаемые при n и деление на 2. Окончательно, сложность алгоритма сортировки выбором будет O(n2).


Ещё в Вашей второй программе можно принять для анализа алгоритм поиска элемента массива (строки 37 и 38). Очевидно, что в худшем случае будут просмотрены все n элементов, иными словами, сложность этого алгоритма O(n).
2
13.06.2017, 16:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.06.2017, 16:55
Помогаю со студенческими работами здесь

Как оценить сложность алгоритма?
К примеру, есть один и второй код. Какая у них сложность? n = mylist = list(set(n)) print...

Как рассчитать сложность алгоритма?
Помогите мне пожалуйста Я не понимаю много о сложности алгоритма. Как рассчитывать сложность...

Как определить временную сложность алгоритма?
Никак не могу разобраться как считается временная сложность алгоритма :с const int counter = P;...

Как узнать сложность алгоритма(ресурсы ,способы)
Здравствуйте, нужно узнать сложность какой-нибудь ф-ии из стандартной библиотеки cpp. Где это можно...

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru