Различия между версиями 2 и 8 (по 6 версиям)
⇤ ← Версия 2 от 2015-12-12 00:39:36 →
Размер: 1676
Редактор: FrBrGeorge
Комментарий:
← Версия 8 от 2015-12-12 22:49:39 → ⇥
Размер: 2654
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 10: Строка 10:
 * Пример эффективной сортировки — слияние
  * Слияние двух отсортированных последовательностей в одну имеет линейную сложность:		  * Слияние двух отсортированных последовательностей в одну имеет линейную сложность:
Строка 17: Строка 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
Строка 25: Строка 26:
 * Пример эффективной сортировки слиянием (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}}}
  * k≤log,,2,,n+1
Строка 27: Строка 38:
  1. Прочитать [[RW:Алгоритм_сортировки|про алгоритмы сортировки в Википедии]]
Строка 29: Строка 40:
  2. Посчиаить кличество оборотов цикл.   1. Посчитать количество оборотов цикла (сравнить с обменной сортировкой)

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

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

    • k≤log2n+1

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

  1. Прочитать про алгоритмы сортировки в Википедии

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

CategoryClass CategoryVmsh

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