Анализ сложности алгоритмов

Сначала научимся считать элементарные инструкции, для этого сделаем несколько предположений. Предположим, что наш процессор способен выполнять, за один такт следующие операции:

  1. Присваивать значение переменной
  2. Находить значение конкретного элемента в массиве
  3. Сравнивать два значения
  4. Инкрементировать значение
  5. Основные арифметические операции (например, сложение и умножение)
  6. Ветвление в операторt if происходит мгновенно

Рассмотрим следующий код и подсчитаем необходимое процессору число тактов для получения результата 

        
        M = A[0]
        for i in range(n):
            if (A[i] >= M):
            M = A[i]
Таблица 1: Специальные названия для функций
f(n) Название
\(1\) За константу
\(\log n\) Логарифмический
\(n\) Линейный
\(n\log n\) ? Log Linear
\(n^{2}\) Квадратичный
\(n^{3}\) Кубический
\(2^{n}\) Экcпоненциальный 
        
        test = 0
        for i in range(n):
           for j in range(n):
              test = test + i * j

Варианты ответов:

1. \(O(2^{n})\)     2. \(O(n)\)     3. \(O(n^{2})\)     \[ 1. O(n)   2. O(n^2)   3. O(log(n))   4. O(n^3) \

Проверить себя:

Правильный ответ 2
        
        test = 0
        for i in range(n):
           test = test + 1
        
        for j in range(n):
           test = test - 1

Варианты ответов:

\[ 1. O(n)   2. O(n^2)   3. O(log(n))   4. O(n^3) \]

Проверить себя:

Правильный ответ 
        
        i = n
        while i > 0:
           k = 2 + 2
           i = i // 2

Варианты ответов:

\[ 1. O(n)   2. O(n^2)   3. O(log(n))   4. O(n^3) \]

Проверить себя:

Правильный ответ

Итераторы

Считается, что объект s поддерживает итерации, если он может использоваться в следующем программном коде, который является отражением реализации инструкции for:

it = s.__iter__() 			# Получить итератор для объекта s
while 1:
    try:
        i = it.__next__() 	# Получить следующий элемент
    except StopIteration:
    break
    ...						# выполнить операции над i

Полиморфизм

Полиморфизм - механизм динамического связывания методов. Вызвать версию метода базового класса внутри одноименного метода подкласса можно с помощью встроенной функции super().

В Питоне отсутствует перегрузка - т.е. возможность иметь в одном классе несколько методов с одинаковыми именами, но с различными списками входных параметров. Отсутствует - управление доступом.

Экземпляры класса создаются посредством обращения к имени класса, как к функции, которой передаются все необходимые аргументы.

По умолчанию все эземпляры классов являются хешируемыми. Но если будет реализован метод __eq__(), экзепляры перестают быть хешируемыми.

Декоратор - это функция, которая в качестве аргумента принимает функцию или метод и возвращает измененную(декорированную) версию.

Статические методы - это методы, которые не получают аргумент self(первый аргумент). Для статических методов используется декоратор staticmethod. Вместо статических методов лучше создавать функции модуля или методы класса.