Differences between revisions 4 and 5
Revision 4 as of 2015-12-12 19:29:52
Size: 2497
Editor: FrBrGeorge
Comment:
Revision 5 as of 2015-12-12 19:43:01
Size: 2495
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 34: Line 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 (last edited 2015-12-12 19:49:39 by FrBrGeorge)