Анализ и построение алгоритмов

  • 25 мая 2011 г.
  • 320 Слова
Технический Университет Молдовы

Отчет
о лабораторной работе №1

по предмету: Анализ и построение алгоритмов

Тема: Сравнение времени работы

Выполнил: студент группы TI-084

Проверил:Кишинев 2009

Цель: Временной анализ функций.

1. Функции, расположенные в порядке уменьшения их эффективности:
0. f(n)= 1/n
1. f(n)= log log n
2. f(n)= ln n
3. f(n)= log n
4. f(n)= n/log n
5. f(n)= √n
6. f(n)= log (n!)
7. f(n)= n
8. f(n)= n log n
9. f(n)= n2
10. f(n)= 2n
11. f(n)= n3
12. f(n)= n!
13. f(n)= n^n
Графики функций:
[pic]
[pic]

[pic]

[pic]
[pic]2. Сравнение алгоритмов:

|A |B |Ơ |ơ |Ω |Ω |Θ |
|Logk n |nε|Нет |да |Нет |Нет |нет |
|nk |cn | Нет |Да |Нет |Нет|нет |
|√n |nsin n |нет |Нет |Нет |Нет |Нет |
|2n |2n/2|нет |Нет |Нет |Да |Нет |
|nlog m |mlog n |нет |Нет |Нет |Нет|Да |
|log (n!) |log (nn) |да |Нет |Нет |Нет |Нет |

Графики функций:
k≥1, ε>0, c, m>1 –некоторые константы
k=2; m=3; ε =3; с=2;

[pic]
[pic]
[pic]
[pic]
[pic]

[pic]
3. Сравнение скорости роста
Функции в порядке увеличения скорости роста:

1. (√2) log n О 2log n

2. 22^nO 22^(n+1)

3. n! O ( n+1)!

4 (log n)! O log (n!)

5. (3/2)n O n*2n O en

6. n O 2n O n2 O n3

7. n log log n...
tracking img