4

И вновь всех приветствую. Решил очередную задачу на контесте способом, который показался мне интересным. Т.к. я новичок, еще не совсем понимаю как определять О(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])

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

2
  • По сложности претензий нет, оптимальное решение, а вот читаемость можно подтянуть. Программы пишутся для людей, а не для компьютера. Иначе все бы до сих пор писали в машинных кодах.
    – extrn
    15 авг 2019 в 14:28
  • @extrn, понял вас, исправлюсь.
    – BaDINGA
    15 авг 2019 в 16:14

1 ответ 1

2

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

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

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

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.