|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
13.11.2009, 10:31 | #1 |
Пользователь
Регистрация: 02.09.2009
Сообщений: 56
|
Сравнение быстродействия алгоритмов
Мне нужно написать программу сравнения быстродействия 2 сортировок. Вот я начала смотреть стаью про то как это можно сделать. И немного непонятен один момент. Расстолкуйте,пожалуйста,если можно.
Быстродействие алгоритма связано с количеством выполняемых операций, поэтому оценить его эффективность можно путем их простого подсчета. Рассмотрим несколько примеров. Связанный список, допускающий обход. Содержимое связанного списка, на который ссылается указатель head, можно вывести на экран с помощью следующего фрагмента программы. N ode * сцг == head; <- 1 присваивание while (cur !== NULL < - п+ 1 сравнений { cout « cur->itetn « endl · < - n операций записи cur == cur->next; <- n присваиваний } // Конец цикла while В предположении, что связанный список состоит из п узлов, эти операторы выполняют n+ 1 присваивание, n+ 1 сравнение и п операций записи.Если каждое присваивание, сравнение и операция записи выполняется за а, Ь и с единиц времени, то на выполнение данного фрагмента программы уйдет (n+ 1) *(а+с) +n *и> единиц времени. Итак, можно интуитивно догадаться, что вывод на экран содержимого 100 узлов связанного списка будет выполняться дольше, чем вывод содержимого 1О узлов. Почему получается именно n+1 присваивание, n+ 1 сравнение и n операций записи??? И что значит знак -> в псевдокоде?? |
13.11.2009, 10:46 | #2 |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
По ходу во всех институтах начали проходить сортировку .
Слушай сюда Птичка . Первое присваивание (которое не n, а +1) Код:
Так что надо просто внимательно посмотреть на прогу. Далее - все это ботва и вилами на воде писано, поскольку не учитываются операции по обслуживанию алгоритма - например выделение памяти из кучи. Память может быть так фрагментирована (я сейчас говорю не о конкретно данном примере), что если в момент выполнения одной из операции (например создание нового элемента) в куче не окажется блока нужного размера? Тогда память будет дефргаментирована, а это процесс не быстрый и главное он не имеет определенного постоянного временного лимита, то есть сейчас он может быть столько-то, а в следующий раз больше (или меньше), либо может вообще не происходить. Далее быстродействие алгоритма также зависит от проца, ОСи, ее настроек, объема ОЗУ и конкретной версии компилятора (и в ряде случаев его настроек тоже - например отсутствие проверки выхода за границы массива также ускоряет алгоритм).
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика Последний раз редактировалось Utkin; 13.11.2009 в 10:54. |
13.11.2009, 10:49 | #3 | |
Заснувший
Форумчанин
Регистрация: 13.03.2009
Сообщений: 213
|
-> - это синтаксис языка С++ для доступа к элементам класса(поля, процедуры и т.д.)
Цитата:
Сначала пройзойдёт первое присваивание N ode *cur = head; Потом произойдёт сравнение условия цикла (cur != NULL) Потом операция записи cout « cur->itetn « endl Затем присвоения cur == cur->next; Всех операций было по одной штуке, кроме операции присоения она существует до цикла и поэтому присвоений получилось n+1. Представь что элемент в этом "массиве" всего один. Будет проверено условие цикла (cur != NULL), а затем выход из него. Но получиться что произошло n+1 сравнений.... |
|
13.11.2009, 11:13 | #4 | |
Пользователь
Регистрация: 02.09.2009
Сообщений: 56
|
Цитата:
Последний раз редактировалось Pti44ka; 13.11.2009 в 11:19. |
|
13.11.2009, 11:24 | #5 | |
Пользователь
Регистрация: 02.09.2009
Сообщений: 56
|
Цитата:
|
|
13.11.2009, 12:23 | #6 | |
Заснувший
Форумчанин
Регистрация: 13.03.2009
Сообщений: 213
|
Цитата:
Почитайте немного теории о циклах(и вообще о программировании). |
|
13.11.2009, 12:55 | #7 | |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Цитата:
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
|
13.11.2009, 13:30 | #8 | |
Пользователь
Регистрация: 02.09.2009
Сообщений: 56
|
Цитата:
А вот этим текстом cur!=null мы говорим про ссылку или про значение узла?? |
|
13.11.2009, 13:36 | #9 | |
Старожил
Регистрация: 04.02.2009
Сообщений: 17,351
|
Цитата:
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
|
13.11.2009, 13:41 | #10 |
Пользователь
Регистрация: 02.09.2009
Сообщений: 56
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Падение быстродействия в макросе | skif93 | Microsoft Office Excel | 8 | 12.04.2009 14:49 |
програмирование алгоритмов | bbk_serg | Помощь студентам | 1 | 01.02.2009 18:29 |
Российский конкурс алгоритмов | Virtson | Свободное общение | 2 | 16.12.2007 21:53 |