6.3. Классификация по сложности
Обычно алгоритмы классифицируют в соответствии с их временной сложностью. Можно выделить следующие их типы:
1. Постоянный - сложность оценивается как O(1).
2. Линейный - оценка равна O(n).
3. Квадратный - O(n2)
4. Кубический, полиноминальный - O(n3),O(nm).
5. Экспоненциальный - O(tp(n)), t- константа, p(n) - некоторая полиномиальная функция.
6. Факториальный - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.
С ростом n временная сложность может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма. Рассмотрим таблицу, в которой сравнивается время выполнения алгоритмов разных типов при n = 106, при условии, что единицей времени для компьютера является микросекунда.
Тип Сложность Кол-во операций Время при 106 операций в сек.
Постоянные O(1) 1 1мкс
Линейные O(n) 106 1 с
Квадратичные O(n2) 1012 11.6 дн.
Кубические O(n3) 1018 32000 лет
Экспоненциальные O(2n) 10301030 в 10301006 раз больше времени
существования Вселенной
23. Легко и труднорешаемые задачи.
1. Приборы комбинации бинарного клюса
0,1
М-символов
а) М=4, L=4*8=32бита
L 32 10 10 10 2
б) 2 =2 =2 * 2 *2 *2 =4млрд
2.Найти наиболее дешевый способ проезда.
N1 M0
N2 M1
N3 M2
N4 M6
N5 M24
#include < stadio.h>
#include <math.h>
Int main ( )
{
Int n total ,x,y.z;
Scanf (“%d”,&n);
Total =3;
While (1)
{
For (x=1; x<=total-2; x++)
For(y=1; y<=total-x-1;y++)
{
Z=total-z-y
If ((int)paw(x,n)+(int)paw(y,n)= =(int)paw(z,n))
Printf(“hello,world!\n”)
}
Totall++
}
Returne 0;
}
Можно создать программу H которая получая на вход текст другой программы выдает сообщение типа:
Далее ограничим H1 следующим образом, она получает на вход только текст программы Р, она отвечает что сделала бы Р если ее входом была оно сама.
Предположим что H2 печатает yes тогда H2 говорит, что H2 получая себя в качестве входа, печатает hello world, но это невозможно.
Невозможно построить программу получающую на вход текст другой программы, и утверждающую что эта входная программа сделает что-то.
Задача или программа это вопрос о принадлежности последовательности символов к языку( формуле формальной теории). Множество языков на любой алфавит нечетно, т.е их невозможно пронумеровать целыми числами.
С другой стороны программы будучи символьными последовательностями образуют счетное множество отсюда следует что проблем сущ-ет бесконечное множество, чем программ которые могут их решить.
Английский математик и физик Пен Роуз показал, что теорема Геделя может использоваться о доказательстве факта различия между компьютером и человеческим мозгом. Компьютер действует строго логически и не может определить истинность или ложность высказывания, если оно лежит за рамкой формальной теории.
Тест Тьюринга
Он придуман для вычислительных систем. Человек взаимодействует с компьютером через устройство связи в течение сколько угодно времени. Человеку необходимо определить с кем он взаимодействует, если он понимает что перед ним машина, значит тест компьютером не пройден.