Форум » Обработка числовых последовательностей » Эффективность по времени » Ответить
Эффективность по времени
mendez: Здравствуйте! Вот текст задачи 82: [more] В вход программы поступают N ≤ 1000 натуральных чисел, каждое из которых не превышает 10000. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N, сумма элементов нечётна, произведение делится на 13, а номера чисел в последовательности отличаются МЕНЕЕ, чем на 5. Напишите эффективную по времени и по памяти программу для решения этой задачи. [/more] Программа, написанная мной на 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:c+=1print(k) k[i%5]=xprint(c)
Ответов - 2
Анна_Л: Вложенный цикл при любом количестве входных данных всегда рассчитан на 5 элементов, так что время обработки будет линейно возрастать с увеличением N. Такие программы вроде считаются эффективными по времени (во всяком случае, по критериям ЕГЭ)
Поляков: mendez пишет: эффективна ли такая программа по времени? Или такой вложенный цикл, как в ней, не сказывается на эффективности? Да, сложность такого алгоритма - линейная, оценивается как O(N), поэтому программа эффективна по времени. Число шагов внутреннего цикла от N не зависит.
полная версия страницы