Сравнение быстродействия алгоритмов

[Pti44ka]

Мне нужно написать программу сравнения быстродействия 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 операций записи??? И что значит знак -> в псевдокоде??

[Utkin]

По ходу во всех институтах начали проходить сортировку .
Слушай сюда Птичка . Первое присваивание (которое не n, а +1)

N ode * сцг == head; <- 1 присваивание

+1 Сравнение нужно как условие выхода из цикла - операции не будут выполнены, но сравнение все равно будет произведено циклом while.
Так что надо просто внимательно посмотреть на прогу.
Далее - все это ботва и вилами на воде писано, поскольку не учитываются операции по обслуживанию алгоритма - например выделение памяти из кучи. Память может быть так фрагментирована (я сейчас говорю не о конкретно данном примере), что если в момент выполнения одной из операции (например создание нового элемента) в куче не окажется блока нужного размера? Тогда память будет дефргаментирована, а это процесс не быстрый и главное он не имеет определенного постоянного временного лимита, то есть сейчас он может быть столько-то, а в следующий раз больше (или меньше), либо может вообще не происходить.
Далее быстродействие алгоритма также зависит от проца, ОСи, ее настроек, объема ОЗУ и конкретной версии компилятора (и в ряде случаев его настроек тоже - например отсутствие проверки выхода за границы массива также ускоряет алгоритм).

[Виталий Серов]

-> - это синтаксис языка С++ для доступа к элементам класса(поля, процедуры и т.д.)

Почему получается именно n+1 присваивание, n+ 1 сравнение и n операций записи

Попробую обьяснить на примере двух повторений твоего цикла:
Сначала пройзойдёт первое присваивание N ode *cur = head;
Потом произойдёт сравнение условия цикла (cur != NULL)
Потом операция записи cout « cur->itetn « endl
Затем присвоения cur == cur->next;
Всех операций было по одной штуке, кроме операции присоения она существует до цикла и поэтому присвоений получилось n+1.
Представь что элемент в этом "массиве" всего один.
Будет проверено условие цикла (cur != NULL), а затем выход из него. Но получиться что произошло n+1 сравнений....

[Pti44ka]

Сообщение от Виталий Серов

-> - это синтаксис языка С++ для доступа к элементам класса(поля, процедуры и т.д.)

Попробую обьяснить на примере двух повторений твоего цикла:
Сначала пройзойдёт первое присваивание N ode *cur = head;
Потом произойдёт сравнение условия цикла (cur != NULL)
Потом операция записи cout « cur->itetn « endl
Затем присвоения cur == cur->next;
Всех операций было по одной штуке, кроме операции присоения она существует до цикла и поэтому присвоений получилось n+1.
Представь что элемент в этом "массиве" всего один.
Будет проверено условие цикла (cur != NULL), а затем выход из него. Но получиться что произошло n+1 сравнений....

УРАААА..Спасибо. Я поняла почему n+1 присваиваний. Получается,что в цикле мы делаем n присваниваний и еще одно присваивание N ode *cur = head перед циклом.А вот почему n+1 сравнений еще не очень понятно((( Хорошо,представим,что элемент 1. Тогда чтобы записать его в head я должна проверить пустая ли эта" ячейка". Если она пустая,то я записываю элемент,если нет то выход из цикла. И у меня получается 1 сравнение,а не 2!!((( Даже если считать + 1 как условие выхода из цикла,то все равно получается n сравнений. Возьмем тот же 1 элемент. Я проверяю пустая ли ячейка,если не пустая то записываю. Получается 1 сравнение,а если эта ячейка занята другими данными,то тоже получается 1 сравнение.

[Pti44ka]

Сообщение от Utkin

По ходу во всех институтах начали проходить сортировку .
Слушай сюда Птичка . Первое присваивание (которое не n, а +1)

N ode * сцг == head; <- 1 присваивание

+1 Сравнение нужно как условие выхода из цикла - операции не будут выполнены, но сравнение все равно будет произведено циклом while.
Так что надо просто внимательно посмотреть на прогу.
Далее - все это ботва и вилами на воде писано, поскольку не учитываются операции по обслуживанию алгоритма - например выделение памяти из кучи. Память может быть так фрагментирована (я сейчас говорю не о конкретно данном примере), что если в момент выполнения одной из операции (например создание нового элемента) в куче не окажется блока нужного размера? Тогда память будет дефргаментирована, а это процесс не быстрый и главное он не имеет определенного постоянного временного лимита, то есть сейчас он может быть столько-то, а в следующий раз больше (или меньше), либо может вообще не происходить.
Далее быстродействие алгоритма также зависит от проца, ОСи, ее настроек, объема ОЗУ и конкретной версии компилятора (и в ряде случаев его настроек тоже - например отсутствие проверки выхода за границы массива также ускоряет алгоритм).

Да согласна, но в статье написано,что при сравнении алгоритмов нужно все делать на одном компьютере и с однима компилятором. Поэтому думаю,что тогда мы сможем получить наиболее правильные результаты. Тогда нам просто не нужно учитывать версию компьютера и компилятора,так как она у нас будет одинаковая при сравнении алгоритмов.

[Виталий Серов]

А вот почему n+1 сравнений еще не очень понятно(((

Сравнение выполняеться как узловие цикла, поэтому если в "массиве" один элемент, то после первого прохода цикла (1 сравнение) произойдёт ещё одно сравнение и выход из цикла. Поэтому и n+1.
Почитайте немного теории о циклах(и вообще о программировании).

[Utkin]

Сообщение от Pti44ka

Да согласна, но в статье написано,что при сравнении алгоритмов нужно все делать на одном компьютере и с однима компилятором. Поэтому думаю,что тогда мы сможем получить наиболее правильные результаты. Тогда нам просто не нужно учитывать версию компьютера и компилятора,так как она у нас будет одинаковая при сравнении алгоритмов.

Для Вашего примера это верно, но для более сложных алгоритмов все равно нужно учитывать работу с кучей.

[Pti44ka]

Сообщение от Виталий Серов

Сравнение выполняеться как узловие цикла, поэтому если в "массиве" один элемент, то после первого прохода цикла (1 сравнение) произойдёт ещё одно сравнение и выход из цикла. Поэтому и n+1.
Почитайте немного теории о циклах(и вообще о программировании).

По-моему, я поняла. Если у нас узел списка содержит данные,то цикл выполняется еще раз и ищет узел,который не содержит их. Если следующий узел снова содержит данные,то цикл выполняется заново. Если мы встречаем узел,который не содердит данных. (тоесть он есть последним в списке),то у нас выполняется только сравнение и мы не заходим в цикл. Поэтому и +1.

А вот этим текстом cur!=null мы говорим про ссылку или про значение узла??

[Utkin]

Сообщение от Pti44ka

По-моему, я поняла. Если у нас узел списка содержит данные,то цикл выполняется еще раз и ищет узел,который не содержит их. Если следующий узел снова содержит данные,то цикл выполняется заново. Если мы встречаем узел,который не содердит данных. (тоесть он есть последним в списке),то у нас выполняется только сравнение и мы не заходим в цикл. Поэтому и +1.

А вот этим текстом cur!=null мы говорим про ссылку или про значение узла??

Сам цикл не ищет ничего, но просто для того что бы выйти из него ВСЕГДА будет на одно сравнение больше. По-крайней мере в твоей ситуации.

[Pti44ka]

Сообщение от Utkin

Сам цикл не ищет ничего, но просто для того что бы выйти из него ВСЕГДА будет на одно сравнение больше. По-крайней мере в твоей ситуации.

Ясно. Спасибо)))