Разместите свой проект бесплатно и начните получать предложения от фрилансеров-исполнителей уже спустя минуты после публикации!
300 ₽

Л/р - Исследование временных характеристик алгоритмов

истекло время актуальности


Алгоритм линейного поиска. Вход: последовательность n чисел A=<a1,…,an> и число v. Выход: индекс i, для которого v=A[i] или NIL, если v не принадлежит А.

Использовать последовательный просмотр при поиске v. Оценить сколько сравнений потребуется алгоритму, если искомым может быть любой элемент массива А (с одинаковой вероятностью). Каково время работы в среднем и в худшем случае? Выразить это время Ө-обозначением. При поиске в отсортированном массиве можно сначала сравнивать искомый элемент со средним элементом массива и, узнав в какой из полученных частей массива находится искомый, продолжить поиск рекурсивно (двоичный поиск).

Написать программу двоичного поиска, учтя время на сортировку, с рекурсией. Определить её Ө.

Сравнить временные характеристики алгоритмов:

·  линейного поиска,

·  сортировки с двоичным поиском,представленными циклами,

·  сортировки с двоичным поиском,представленными рекурсией.

Полное описание лабораторной работы в прикрепленном файле

Приложения 1

Просмотр приложений доступен только зарегистрированным пользователям.


  1.  фрилансер больше не работает на сервисе
  • вам надо написать прогу которая ищет тремя способами или посчитать сложности этих троих алгоритмов? или и то и то? в любом случае 300 руб не то

  • Валерий Калач — заказчик проекта
    Пожаловаться | 16 мая в 22:11 |

    Вот еще два варианта, мне подойдет любой, может для вас попроще будет какой?

    Вариант 3.

    Цикл While процедуры “Сортировка вставками просматривает элементы отсортированного    участка А[1…j-1] подряд. 

    Вместо последовательного просмотра использовать двоичный поиск. Определить    Ө для двоичного поиска.Удастся ли таким образом сделать общее время сортировки    Ө(n log n)?

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

    Сравнить временные характеристики трёх алгоритмов: вставками, вставками с двоичным    поиском и рекурсией, с двоичным поиском циклами.


    Вариант 6

    Оформить сортировку вставками как рекурсивную процедуру: желая сортировать    A[1..n], мы (рекурсивно) сортируем A[1..n-1], а затем ставим A[n] на правильное    место в отсортированном массиве A[1..n-1].
      Написать рекуррентные отношения для времени работы такой процедуры и найти оценку    O(g(n))=T(n).

    Сравнить эту оценку с начальной сортировкой вставками и слиянием.

  • да мне ровно какой вариант, алгоритмы на уровне, их оценка тоже, вопрос что вам надо, прога или теоретическое исследование или и то и то и какой бюджет, вы готовы умножить написанное на 5?

  • Валерий Калач — заказчик проекта
    Пожаловаться | 16 мая в 22:33 |

    Та за штуку сам препод мне эту лабу простит 🙂, это же не курсач, я и сам с джавой дружу и прогу нарисую, но этих алгоритмов не понимаю, сама задача мне не понятна

  • пока что на ваши копейки желающих не нашлось) идите к преподу)

  • Валерий Калач — заказчик проекта
    Пожаловаться | 16 мая в 23:22 |

    нее, нашел исполнителя за 600 рублей на другой площадке 🙂

  • рад за вас

  • Валерий Калач — заказчик проекта
    Пожаловаться | 16 мая в 23:32 |

    Спасибо! Удачи вам!

  • Добавить

Заказчик
Валерий Калач
Украина Полтава  1   0
Проект опубликован
16 мая в 21:31
37 просмотров
Поделиться