Differences between revisions 2 and 3
Revision 2 as of 2015-12-11 21:39:36
Size: 1676
Editor: FrBrGeorge
Comment:
Revision 3 as of 2015-12-11 21:42:05
Size: 1829
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 25: Line 25:
  * Сольём все подряд идущие пары значений '''TODO'''
Line 29: Line 30:
  2. Посчиаить кличество оборотов цикл.   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
    • Сольём все подряд идущие пары значений TODO

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

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


CategoryClass CategoryVmsh

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