Математическая логика и теория алгоритмов
| Категория реферата: Рефераты по математике
| Теги реферата: скачать реферат по истории, курсовая работа по управлению
| Добавил(а) на сайт: Дросида.
Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата
end;
end.
Расчёт вычислительной сложности.Емкостная сложность:
В программе используется одномерный массив размерности 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 |
Категории:Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата Поделитесь этой записью или добавьте в закладки |
|
Главная