Додайте свій проект безкоштовно і почніть отримувати пропозиції від фрілансерів-виконавців вже через хвилини після публікації!
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 переглядів
Поділитися