Анализ эффективности алгоритмов

Автор работы: Пользователь скрыл имя, 11 Января 2013 в 01:50, курсовая работа

Описание работы

Цель исследования: Выявить и систематизировать материалы по теме: «Анализ эффективности алгоритмов».
Задачи Исследования:
• Изучить литературу по теме исследования;
• Систематизировать теоретический материал;
• Выполнить практическую часть, состоящую их 4-х заданий.

Содержание работы

Введение 3
Теоретическая часть 4
I. Измерение эффективности алгоритмов 4
II. О-сложность алгоритмов 7
Практическая часть 14
Задание 1 14
Задание 2 16
Задание 3 20
Задание 4 21
Заключение 25
Список использованной литературы

Скачать архив (195.19 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

Теоретические основы информатики.doc

— 401.00 Кб (Скачать файл)

 

 

Турниров:

                                          1012

                            1012                     1158

            1012                    1117                   1158

   1380        1012         2154       1117         1158    1340

1380  2341  1012 2643 2154 2425 1826 1117  1158  1429 1340

 

 

 

 

                                       1117

                           1117                 1340

            1380                      1117          1340

    1380         2154        1826          1117        1340

1380  2341  2643 2154  2425 1826  1117  1158 1429 1340

 

                                      1158

                            1158               1340

             1380                     1158     1340

    1380          2154         1826       1158   1340

1380  2341  2643 2154  2425 1826  1158 1429 1340             

 

 

                             1340                                                                   

                     1380            1340                                                                  

         1380        2154         1826         1340                    

    1380  2341  2641  2154  2425  1826 1429 1340        

 

 

 

 

                          1380

            1380                        1429

      1380      2154           1826   1429

   1380  2341  2641  2154 2425  1826 1429

 

 

 

                         1429                                                            1826

                  2154     1429                                                 2154   1826

      2341           2154       1429                                   2341          2154  1826

  2341  2641  2154  2425  1826 1429                   2341  2641  2154  2425  1826

 

 

         2154                                       2341

    2341         2154                         2341   2425                      2425

  2341  2641  2154  2425             2341  2641  2425           2641  2425         2641

 

 

 

 

 

 

Простых вставок:

1380  2341  1012 2643 2154 2425 1826  1117  1158 1429 1340

 

1380  2341  1012 2643 2154 2425 1826  1117  1158 1429 1340

1380  2341  1012 2643 2154 2425 1826  1117  1158 1429 1340

1012  1380  2341  2643 2154 2425 1826  1117  1158 1429 1340

1012  1117  1380  2341  2643 2154 2425 1826  1158 1429 1340

1012  1117  1158  1380  2341  2643 2154 2425 1826 1429 1340

1012  1117  1158  1340 1380  2341  2643 2154 2425 1826 1429

1012  1117  1158  1340 1380  1429 2341  2643 2154 2425 1826

1012  1117  1158  1340 1380  1429 1826  2341  2643 2154 2425

1012  1117  1158  1340 1380  1429 1826  2154   2341 2643 2425

1012  1117  1158  1340 1380  1429 1826  2154   2341 2425  2643

 

 

Пузырька:

1380  2341  1012 2643 2154 2425 1826  1117  1158 1429 1340

1380  2341  1012 2643 2154 2425 1826  1117  1158 1429 1340

1012  2341  1380 2643 2154 2425 1826  1117  1158 1429 1340

1012  1117  1380 2643 2154 2425 1826  2341  1158 1429 1340

1012  1117  1158 2643 2154 2425 1826  2341  1380 1429 1340

1012  1117  1158 1340 2154 2425 1826  2341  1380 1429 2643

1012  1117  1158 1340 1380 2425 1826  2341  2154 1429 2643

1012  1117  1158 1340 1380 1429 1826  2341  2154 2425 2643

1012  1117  1158 1340 1380 1429 1826  2154  2341 2425 2643

 

В процессе применения методов  подсчитать число выполняемых операций сравнения и заполнить таблицу  следующего вида (n -  длина сортируемой последовательности):

 

Метод

Tmax

Число выполненных  сравнений S

Δ=Tmax-S

турниров

(n-1)+(n-1)log2n= (11-1) + (11-1)log211=20log211=60,5

44

60,5-44=16,5

простых

вставок

= 60,5

8

60,5-8=52,5

пузырька

= 60,5

7

60,5-7=53,5


 

 

 

Метод

 

Тср

Число выполненных сравнений S

 

простого перебора

= (11+1)/2=6

10

|6-10|=4

двоичного

поиска

=

 =

= 6*3.6-1= 20.5

3

20.5-3 = 17.5

деревьев сравнений 

1,39log2 n = 1,39log211 = 4.8

4

4.8-4=0.8


 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

Мы рассмотрели  эффективность  алгоритмов, пользуясь точными оценками.  Показано, что эффективность алгоритмов сортировки оценивается относительно легко.

В ходе проведения исследования:

— исследовали теоретический  материал: анализ эффективности алгоритмов

— исследовали практический материал

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы

 

  1. Информатика: учебник Автор: Соболь Б.В., Галин А.Б., Панов Ю.В.,Рашидова Е.В., Садовой Н.Н. Издательство: Ростов н/Д: Феникс Год: 2007 Страниц: 446.
  2. Электронно-библиотечная система (ЭБС) ООО «Издательский Дом ИНФРА_М» (доступ через интернет репозиторий образовательных ресурсов ВЗФЭИ). – URL: http://repository.vzfei.ru. Доступ по логину и паролю.
  3. Информатика в экономике: учебное пособие / под ред.Б.Е. Одинцова, А.Н. Романова. – М.: Вузовский учебник, 2008.
  4. Галушкина Ю.Н., Марьянов А.Н. Конспект лекций по дискретной математике. – М.: Айрис_пресс, 2007.

 

 

 

 

 

 

 

 

 

 


 



Информация о работе Анализ эффективности алгоритмов