Автор | Сообщение |
|
Отправлено: 20.03.19 13:23. Заголовок: Эффективность по времени
Здравствуйте! Вот текст задачи 82: Скрытый текст В вход программы поступают N ≤ 1000 натуральных чисел, каждое из которых не превышает 10000. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N, сумма элементов нечётна, произведение делится на 13, а номера чисел в последовательности отличаются МЕНЕЕ, чем на 5. Напишите эффективную по времени и по памяти программу для решения этой задачи.
| Программа, написанная мной на Python, по сути дела, проверяет все возможные пары (то есть такие, номера которых отличаются менее, чем на 5), при этом не запоминая их в общем массиве, а обрабатывая по ходу. Ниже приведен ее код. Ясно, что по памяти она эффективна, но вопрос: эффективна ли такая программа по времени? Или такой вложенный цикл, как в ней, не сказывается на эффективности? N=int(input()); c=0; k=[0]*5 for i in range(N):x= int(input()) for j in [k[i%5-4], k[i%5-3], k[i%5-2], k[i%5-1]]:if j!=0:if (j*x)%13==0 and (j+x)%2==1: print(c)
|
|
|
Ответов - 2
[только новые]
|
|
|
Отправлено: 22.03.19 16:59. Заголовок: Вложенный цикл при л..
Вложенный цикл при любом количестве входных данных всегда рассчитан на 5 элементов, так что время обработки будет линейно возрастать с увеличением N. Такие программы вроде считаются эффективными по времени (во всяком случае, по критериям ЕГЭ)
|
|
|
|
| Администратор
|
Сообщение: 1846
|
|
Отправлено: 22.03.19 23:09. Заголовок: mendez пишет: эффект..
mendez пишет: цитата: | эффективна ли такая программа по времени? Или такой вложенный цикл, как в ней, не сказывается на эффективности? |
|
Да, сложность такого алгоритма - линейная, оценивается как O(N), поэтому программа эффективна по времени. Число шагов внутреннего цикла от N не зависит.
|
|
|
|