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

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

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) \

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

          
          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. Вместо статических методов лучше создавать функции модуля или методы класса.