Различия между версиями 2 и 3
⇤ ← Версия 2 от 2015-12-12 00:39:36 →
Размер: 1676
Редактор: FrBrGeorge
Комментарий:
← Версия 3 от 2015-12-12 00:42:05 → ⇥
Размер: 1829
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 25: Строка 25:
  * Сольём все подряд идущие пары значений '''TODO'''
Строка 29: Строка 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 (последним исправлял пользователь FrBrGeorge 2015-12-12 22:49:39)