Различия между версиями 4 и 5
Версия 4 от 2015-12-12 22:29:52
Размер: 2497
Редактор: FrBrGeorge
Комментарий:
Версия 5 от 2015-12-12 22:43:01
Размер: 2495
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 34: Строка 34:
  * Сольём все подряд идущие 2^^k^^   * Сольём все подряд идущие 2^k^

Понятие об оценке сложности

  • Рост функции: константа, логарифм, линейный, квадратичный (степенной), показательной.
  • Поиск и бинарный поиск в отсортированных последовательностях методом половинного деления, оценка сложности
  • Сортировка
  • Оценка сложности сортировки (выбором и пузырём)
  • Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
    •   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

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

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


CategoryClass CategoryVmsh

LecturesVMSH/Python/2015-12-11 (последним исправлял пользователь FrBrGeorge 2015-12-12 22:49:39)