Differences between revisions 3 and 4
Revision 3 as of 2015-12-11 21:42:05
Size: 1829
Editor: FrBrGeorge
Comment:
Revision 4 as of 2015-12-12 19:29:52
Size: 2497
Editor: FrBrGeorge
Comment:
Deletions are marked like this. Additions are marked like this.
Line 10: Line 10:
 * Пример эффективной сортировки — слияние
 
* Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
 * Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
Line 17: Line 16:
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
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
Line 25: Line 26:
  * Сольём все подряд идущие пары значений '''TODO'''  * Пример эффективной сортировки слиянием (n*log,,2,,n)
  {{{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}}}
  * Сольём все подряд идущие 2^^k^^
  {{{0 1 1 2 2 3 3 4 4 5 5 5 6 7 7 8}}}

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

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