Differences between revisions 1 and 2
Revision 1 as of 2015-12-11 13:20:27
Size: 2032
Editor: FrBrGeorge
Comment:
Revision 2 as of 2015-12-11 21:39:36
Size: 1676
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 5: Line 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
  }}}
Line 8: Line 26:
 
Line 11: Line 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

Домашнее задание

  1. Реализовать сортировку слиянием
  2. Посчиаить кличество оборотов цикл.


CategoryClass CategoryVmsh

LecturesVMSH/Python/2015-12-11 (last edited 2015-12-12 19:49:39 by FrBrGeorge)