Математическая логика и теория алгоритмов (стр. 2 из 2)
Емкостная сложность:
В программе используется одномерный массив размерности n, поэтому объём входа и объём выхода совпадают и равны n. Количество пременных равно 3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
Временная сложность:
Если рассматривать обработку каждого листа, без проверки на пути к нему, то временная сложность T(n) = n0+n1+n2+n3+…+nn .
Но в случае, когда каждая вершина проверяется, временная сложность T(n) = o(n0+n1+n2+n3+…+nn). И это тем вернее, чем больше n. Данный вывод получен на основе приведённых ниже статистических данных:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | |
| Общее кол-во листьев | 2 | 7 | 40 | 341 | 3906 | 55987 | 960800 |
| Кол-во вершин построенного дерева. | 2 | 3 | 4 | 17 | 54 | 153 | 552 |
| Время построения(сек) | <0.01 | <0.01 | <0.01 | <0.01 | <0.01 | <0.01 | <0.01 |
| 8 | 9 | 10 | 11 | 12 | 13 | |
| Общее кол-во листьев |  |  |  |  |  |  |
| Кол-во вершин построенного дерева. | 2057 | 8394 | 35539 | 166926 | 856189 | 4674890 |
| Время построения(сек) | <0.01 | 0.21 | 1.20 | 6.48 | 37.12 | 231.29 |
Тестирование.
Построенная по описанному алгоритму программа при различных n выдаёт следующие данные:
n=4
<1,2><2,4><3,1><4,3>
<1,3><2,1><3,4><4,2>
Т.е. количество расстановок равно 2. Ниже приведена таблица зависимости от n количества решений (R).
| n = | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| R= | 1 | 0 | 0 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14200 | 73712 |
Cписок литературы.
1) Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
2) Евстигнеев В.А. Применение теории графов в программировании. – М.:Наука, 1984.
3) Основной алгоритм находился на BBS “Master of Univercity” в файле shen.rar в файловой области “Bardak” (тел. 43-27-03; время работы 21.00 – 7.00; FTN адрес – 2:5090/58).