|
Размер: 2032
Комментарий:
|
Размер: 2497
Комментарий:
|
| Удаления помечены так. | Добавления помечены так. |
| Строка 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 . . 9 7 7 7 7 7 7 7 6 6 6 6 6 6 5 5 5 5 5 4 4 4 4 3 3 3 2 2 1 оставшийся хвост дописываем в конец 0 }}} * Пример эффективной сортировки слиянием (n*log,,2,,n) {{{1; 2; 7; 1; 7; 3; 8; 5; 5; 5; 6; 4; 4; 0; 3; 2}}} * Сольём все подряд идущие пары элементов, получим упорядоченные пары {{{1 2; 1 7; 3 7; 5 8; 5 5; 4 6; 0 4; 2 3}}} * Сольём все подряд идущие четвёрки, получим упорядоченные четвёрки {{{1 1 2 7; 3 5 7 8; 4 5 5 6; 0 2 3 4}}} * … {{{1 1 2 3 5 7 7 8; 0 2 3 4 4 5 5 6}}} * Сольём все подряд идущие 2^^k^^ {{{0 1 1 2 2 3 3 4 4 5 5 5 6 7 7 8}}} |
| Строка 8: | Строка 37: |
| Строка 11: | Строка 39: |
| 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 . . 9 7 7 7 7 7 7 7 6 6 6 6 6 6 5 5 5 5 5 4 4 4 4 3 3 3 2 2 1 оставшийся хвост дописываем в конец 0
Пример эффективной сортировки слиянием (n*log2n)
1; 2; 7; 1; 7; 3; 8; 5; 5; 5; 6; 4; 4; 0; 3; 2
- Сольём все подряд идущие пары элементов, получим упорядоченные пары
1 2; 1 7; 3 7; 5 8; 5 5; 4 6; 0 4; 2 3
- Сольём все подряд идущие четвёрки, получим упорядоченные четвёрки
1 1 2 7; 3 5 7 8; 4 5 5 6; 0 2 3 4
- …
1 1 2 3 5 7 7 8; 0 2 3 4 4 5 5 6
Сольём все подряд идущие 2k 0 1 1 2 2 3 3 4 4 5 5 5 6 7 7 8
Домашнее задание
- Реализовать сортировку слиянием
- Посчитать количество оборотов цикла (сравнить с обменной сортировкой)