⇤ ← Версия 1 от 2015-12-11 16:20:27
2032
Комментарий:
|
1676
|
Удаления помечены так. | Добавления помечены так. |
Строка 5: | Строка 5: |
= Поиск подстроки в строке = [[/PiFunction|Основная статья]] |
= Понятие об оценке сложности = * Рост функции: константа, логарифм, линейный, квадратичный (степенной), показательной. * Поиск и бинарный поиск в отсортированных последовательностях методом половинного деления, оценка сложности * Сортировка * Оценка сложности сортировки (выбором и пузырём) * Пример эффективной сортировки — слияние * Слияние двух отсортированных последовательностей в одну имеет линейную сложность: {{{ 0 2 1 2 0 0 0 3 4 3 1 2 1 1 0 6 5 6 4 3 4 2 4 2 1 2 0 0 0 7<9 . 7>5 9 6>5 9 3<5 9 3<4 9 3>1 9 2>1 9 . 1 9 оставшийся хвост дописываем в конец 7 7 7 7 7 7 6 6 6 6 6 5 5 5 5 4 4 4 3 3 2 }}} |
Строка 8: | Строка 26: |
Строка 11: | Строка 28: |
1. {i} Если описание П-функции в аудитории не слишком понятно, поискать [[http://e-maxx.ru/algo/prefix_function|другие в сети]] 1. Реализовать работающую функцию поиска подстроки в строке 1. Дана строка s длины n. Требуется посчитать количество её различных подстрок. * Решить как-нибудь * Реализовать алгоритм [[http://e-maxx.ru/algo/prefix_function#header_11|Количество различных подстрок в строке]] * Сравнить время работы на больших строках (написать генератор больших строк) 1. Дана строка s длины n. Требуется найти самое короткое её "сжатое" представление, т.е. найти такую строку t наименьшей длины, что s можно представить в виде конкатенации одной или нескольких копий t. * Решить как-нибудь * Реализовать алгоритм [[http://e-maxx.ru/algo/prefix_function#header_12|Cжатие строки]] * Сравнить время работы на больших строках (написать генератор больших строк) ==== Условные обозначения ==== . {o} — тема по Linux . <!> — тема повышенной сложности . {i} — теоретическое задание . {*} — тема для самостоятельного изучения |
1. Реализовать сортировку слиянием 2. Посчиаить кличество оборотов цикл. |
Понятие об оценке сложности
- Рост функции: константа, логарифм, линейный, квадратичный (степенной), показательной.
- Поиск и бинарный поиск в отсортированных последовательностях методом половинного деления, оценка сложности
- Сортировка
- Оценка сложности сортировки (выбором и пузырём)
- Пример эффективной сортировки — слияние
- Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
0 2 1 2 0 0 0 3 4 3 1 2 1 1 0 6 5 6 4 3 4 2 4 2 1 2 0 0 0 7<9 . 7>5 9 6>5 9 3<5 9 3<4 9 3>1 9 2>1 9 . 1 9 оставшийся хвост дописываем в конец 7 7 7 7 7 7 6 6 6 6 6 5 5 5 5 4 4 4 3 3 2
- Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
Домашнее задание
- Реализовать сортировку слиянием
- Посчиаить кличество оборотов цикл.