Насколько эффективен мой метод решения?

#python #python_3x #инспекция_кода #комбинаторика #сложность

И вновь всех приветствую. Решил очередную задачу на контесте способом, который показался
мне интересным. Т.к. я новичок, еще не совсем понимаю как определять О(n), поэтому
прошу помощи в этом вопросе.

Собственно, вот сама задача:


  На вход программы поступает последовательность из N целых
  положительных чисел. Рассматриваются все пары различных элементов
  последовательности  (элементы пары не обязаны стоять в
  последовательности рядом, порядок элементов в паре неважен). 
  Необходимо определить количество пар, сумма чисел и разность индексов
  которых кратна 3.


И мое решение:

n = int(input())
summ = 0
r = [[0] * 3 for i in range(3)]
for i in range(n):
    s = int(input())
    r[i % 3][s % 3] += 1
print((r[0][0] * (r[0][0] - 1) + r[1][0] * (r[1][0] - 1) + r[2][0] * (r[2][0] - 1))//2
+ r[0][1] * r[0][2] + r[1][1] * r[1][2] + r[2][1] * r[2][2])


Проверку на контесте прошла, результат - задача решена верно.
    

Ответы

Ответ 1

Решение отличное, сложность линейная от размера ввода

В цикле выполняется k*n операций, где k - константа, так что его сложность O(n)

Начальные строчки выполняются за константное время O(1), финальная тоже, итого

O(n + 1 + 1) = O(n)