Лабораторная работа 1. Методы сортировки. Лабораторная работа 3. Методы поиска подстроки в строке.
Лабораторная работа 1. Методы сортировки.
Задание
Реализовать заданный метод сортировки строк числовой матрицы в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию быстрой сортировки (quicksort). Оценить время работы каждого алгоритма сортировки и сравнить его со временем стандартной функции сортировки, используемой в выбранном языке программирования.
Вариант 2. Сортировка Вставкой
Выводы
В проделанной работы были реализованы алгоритмы быстрой сортировки (quicksort) и сортировки вставками (insertion sort). Оба алгоритма работают достаточно быстро, но скорость сортировки ставками в среднем ниже, чем скорость быстрой сортировки, так как число операций в среднем случае для быстрой сортировки – 0(nln(n)) , а сортировки вставками - 0(n2)
Лабораторная работа 3. Методы поиска подстроки в строке.
Задание
Реализовать заданный метод поиска подстроки в строке в соответствии с индивидуальным заданием. Для всех вариантов добавить реализацию добавления строк, ввода подстроки и поиска подстроки. Предусмотреть возможность существования пробела. Ввести опцию чувствительности / нечувствительности к регистру. Оценить время работы каждого алгоритма поиска и сравнить его со временем работы стандартной функции поиска, используемой в выбранном языке программирования.
Четный номер по журналу: Кнута-Морриса-Пратта
Выводы
В данной работе реализован алгоритм Кнута-Морриса-Пратта поиска подстроки в строке. Таблица префиксов вычислена за O(m) сравнений, где m - длина поисковой строки, перед началом поиска. А поскольку строка для поиска пройдена ровно один раз, суммарное время работы алгоритма O(m+n), где n — длина текста .
