Выполнение программы требует времени и памяти и зависит от скорости обработки компьютера, на котором выполняется программа. Выполнение фрагмента кода на моем компьютере может занять 1 секунду, в то время как тот же код может занять больше или меньше времени на другом компьютере в зависимости от его вычислительной мощности. Это означает, что мы не можем измерить производительность кода на основе времени выполнения, и она не должна зависеть от ресурсов компьютера.

Хороший код имеет два качества:

  • Читаемость
  • Масштабируемость

Читаемость означает, что код удобочитаем и легок для понимания разработчиками. Обычно это означает, что код должен иметь надлежащие стили кодирования, форматы, соглашения об именах и комментарии, чтобы другим разработчикам было легко работать с вашим кодом.

Масштабируемость означает, что код должен легко масштабироваться для больших входных данных и не должен ломаться. Например, если у приложения в настоящее время тысячи пользователей, а в будущем база пользователей вырастет до миллионов, приложение должно работать так же. Для разработки масштабируемых приложений выполняется большой O-анализ кода, и код делается максимально эффективным.

Обозначение Big O используется для оценки матрицы производительности кода с точки зрения пространственной и временной сложности. Он сообщает, насколько хорошо код будет работать для больших входных данных, оценивая время выполнения и пространство независимо от оборудования, на котором он выполняется.

Сложность времени:оценочное количество времени, необходимое для выполнения

Следующие пункты помогут вам рассчитать большую временную сложность кода:

  • Большой O =, +, -, *, /, % равен 0 (1)
  • Большой O цикла - это O (N), где N - количество выполнений цикла.
  • Big O всегда оценивается для наихудшего сценария
  • Как правило, O(1) + O(1) +… = O(1) и O(N) + O(N) +…= O(N)
  • Кроме того, мы пренебрегаем постоянными терминами и присваиваниями и вычисляем только Big O циклов и дорогостоящих операций.
  • Большой O вложенного цикла равен O(N) * O(N) = O(N²)
  • Для разных входов вложенных циклов O(N) * O(M) = O(N*M) = O(P)

Рассмотрим этот код:

def TwoSum(numbers, target):
    mapValues = {}                                     O(1)
    for i in range(len(numbers)):                      O(N):N=length
        currentVal = mapValues.get(numbers[i], None)   O(1)
        if(currentVal is not None):                    O(1)
            return [currentVal, i]                     O(1)
        else:
            numberToFind = target - numbers[i]         O(1)
            mapValues[numberToFind] = i                0(1)
    return None                                        O(1)

Note: Statements inside loop will execute N=length of numbers times, so their complexity will be multiplied with O(N)
Big O = O(1) + O(N)*(O(1) + O(1) + O(1) + O(1) + O(1)) + O(1)
As O(1) + O(1) +O(1) + ... = O(1), so
      = O(1) + O(N)*(O(1) + O(1)
Also O(1) + O(N) = O(N) and O(1)*O(N) = O(N)
      = O(1) + O(N) + O(1)
      = O(N)

O(N) — это общий термин, где N означает большое число. Мы можем оценить, что N/2, N/3 равны N, когда N слишком велико.

Теперь мы видим, что в конечном итоге сложность зависит от того, сколько раз выполняется цикл, и обычно она не рассчитывается для небольших операций, таких как вычисления и присваивания.

Пространственная сложность:оценочный объем памяти, необходимый программе.

Space Complexity рассчитывается с точки зрения инициализации переменных внутри программы. Сложность пространства зависит от:

  • Переменные
  • Структуры данных
  • Вызовы функций
  • Распределения

Рассмотрим пример ниже для лучшего понимания:

newArray = []                O(1)
for i in range(n):
    newArray.append(i);      O(N)
Big O = O(1) + O(N) = O(N)

Здесь сложность пространства равна O(N), потому что новая память выделяется для массива N раз.

Для расчета большого O обычно считается, что количество входных данных очень велико, и, следовательно, небольшими операциями можно пренебречь, учитываются только повторяющиеся операции.