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

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

  •   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*log₂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₂n+1

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

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

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

CategoryClass CategoryVmsh