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

Что значит сложность алгоритма и зачем нам ее знать? 
Для составления эффективного и оптимизированного по времени и по памяти алгоритма.
Сложность алгоритма обычно вычисляют для больших объемов данных, например, массивы из N элементов. 
Она бывает временная (по используемому времени выполнения) и емкостная (по размеру используемой памяти) и выражается как функция от N. Ее можно вычислить, зная сколько арифметических операций используется в алгоритме и сколько байт занимают данные. 

Кроме этого на эффективность алгоритма (точнее программы) влияет:

•  работа процессора (количество операций выполняемых в секунду), 
•  его разрядность (сколько бит считывается сразу, как одно слово), 
•  устройство памяти,
•  компилятор языка программирования (быстрее будет программа на Ассемблере).

Вот некоторые рекомендации:

• Разрядность процессора должна совпадать с размером данных. Например, 32-х разрядный процессор будет быстрее выполнять операции с типами данных, которые кратны 32 (в Паскале - longint). Это относится и к размеру массива.
• Цикл for работает быстрее while, так как не проверяет условие продолжения/окончания цикла каждый раз.
• В логическом выражении ставьте первым то условие, которое выполняется чаще других. То же относится ко вложенным циклам и циклам с условиями.
• Лучше использовать цикл вместо рекурсивной функции.
• Ввод и вывод на экран тратится больше времени, чем при работе с файлом. Лучше работать напрямую с памятью (лучше динамической).
• По возможности сохраняйте громоздкие вычисления в переменные или константы.
• Вызов функций и подпрограмм тоже требует времени.
• Если есть возможность - сразу считываем, обрабатываем и выводим результат. В некоторых задачах использование массива необязательно, например: в массиве, состоящий из целых чисел, подсчитать количество положительных чисел.

program project1;
var i,n,k,a:int64;//64 разрядный тип целых чисел
begin
 read(n);
 k:=0;
 for i:=1 to n do begin
  read(a);
  if a>0 then k:=k+1;
end;
write(k);

end.

Рассмотрим еще одну задачу, где можно обойтись без массива:
Напишите программу, которая циклически сдвигает элементы массива влево (например, массив {3, 5, 7, 9} превращается в массив {5, 7, 9, 3}).

Решение:
var
n:integer;
a,i,p:longint;
begin
 read(n);read(p);
 for i:=1 to n do begin
  read(a); 
  write(a,' ');
 end;
 write(p);
end.

Здесь сложность алгоритма, не учитывая время на ввод и вывод данных,  равна 0.

Рассмотрим аналогичную задачу, где без массива не обойтись:
Напишите программу, которая циклически сдвигает элементы массива вправо (например, если элементы нумеруются, начиная с нуля, то 0-й элемент становится 1-м, 1-й становится 2-м, ..., последний становится 0-м, то есть массив {3, 5, 7, 9} превращается в массив {9, 3, 5, 7}). (см. здесь)

Решение:
1. Считываем сразу все элементы в нужном порядке и выводим:
program A1;
var
n:integer;
a:array[1..3200] of longint;
i:longint;
begin
 read(n);
 for i:=2 to n do read(a[i]);
 read(a[1]);
 for i:=1 to n do write(a[i],' ');
end.
Здесь сложность алгоритма, не учитывая время на ввод и вывод данных,  равна 0.

2. После считывания всех элементов - делаем сдвиг с конца.
program A2;
var
n:integer;
a:array[1..3200] of longint;
i,p:longint;
begin
 read(n);
 for i:=1 to n do read(a[i]);
 p:=a[n];
for i:=n downto 2 do a[i]:=a[i-1];
a[1]:=p;
 for i:=1 to n do write(a[i],' ');
end.
По количеству присваиваний - сложность алгоритма линейно зависит от N+1.

3. После считывания всех элементов - делаем перестановки пары элементов с конца (как в сортировке пузырьком).
program A3;
var
n:integer;
a:array[1..3200] of longint;
i,p:longint;
begin
 read(n);
 for i:=1 to n do read(a[i]);
 for i:=n downto 2 do begin
  p:=a[i];a[i]:=a[i-1];a[1-1]:=p;
 end;
 for i:=1 to n do write(a[i],' ');
end.
По количеству присваиваний - сложность алгоритма линейно зависит от 3*(N-1).

Еще пример: Дан массив чисел. Переставить элементы массива в обратном порядке.

Решение: Если больше ничего с этим массивом делать не надо, то можно просто считать и вывести за один проход.

program A1;
var
n:integer;
a:array[1..3200] of longint;
i:longint;
begin
 read(n);
 for i:=1 to n do read(a[i]);
 for i:=n downto 1 do write(a[i],' ');
end.

или так

program A2;
var
n:integer;
a:array[1..3200] of longint;
i:longint;
begin
 read(n);
 for i:=n downto 1 do read(a[i]);
 for i:=1 to n do write(a[i],' ');
end.

Если действительно нужно перевернуть массив, то придется написать алгоритм:


program A3;
var
n:integer;
a:array[1..3200] of longint;
p,i:longint;
begin
 read(n);
 for i:=1 to n do read(a[i]);
 for i:=1 to n div 2 do begin
   p:=a[i]; a[i]:=a[n-i+1]; a[n-i+1]:=p; 
 end;
 for i:=1 to n do write(a[i],' ');
end.