0

Я ученик 11 класса(Сдаю информатику). Вопрос в следующем: Циклы в циклах. Из-за них сильно падает эффективность программы. Я слышал, что есть способы, дабы увеличить эффективность программы по времени(Подкорректировать код) Подскажите, как мне разобраться с этой проблемой... Пример: Даны 2 численных массива. Найдите количество пар, суммы чисел которых равна 2 (Примерный вид(Очень упрощенный))

Я не знаю многих терминов и не понимаю свою проблему. Спасибо за уделённое внимание.

3
  • Столько воды, а так и не написано, в чём собственно проблема-то.
    – andreymal
    16 мая 2020 в 0:12
  • Как сделать команду более эффективной по времени. Чем заменить цикл в цикле
    – GeMiX
    16 мая 2020 в 1:00
  • 1
    Перефразируя в медицину - "как сделать, чтоб живот не болел?" - не рассматривая причины, как сказать - делать ли операцию по удалению аппендицита, пить уголек или, напротив, слабительное? Надо смотреть каждую конкретную задачу и искать лучшие алгоритмы. Общего пути, как ускорить вложенные циклы, нет.
    – Harry
    16 мая 2020 в 8:10

2 ответа 2

8

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

Дано:
длина первого массива: n
длина второго массива: m

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

first_arr = [1, 3, 2, 9, 5, 2, 3, 1, 4, 1, 0, -1, -2, -4, 2, 3, 10, 12, -9]
second_arr = [5, 2, 1, 0, -2, -3, 4, 5, -10, -9, -2, -6, 8, 12, 34, 3, 9, 19]

result = 0

for i in first_arr:
    for j in second_arr:
        if i + j == 2:
            result += 1

print(result)

В таком случае количество операций будет не меньше n * m.

Можно заметить, что, если мы отсортируем второй массив за O(n*log(n)), то нам будет легче искать элементы в нем. Тогда пройдясь по всем элементам первого массива мы с помощью бинарного поиска сможем найти элемент, дополняющий его в сумме до 2. Ну или сказать, что такового нет. Бинарный поиск это O(log(n)) и как итог получится O(n*log(n) + n*log(m)). Ну это получше конечно чуть чуть, но далеко от идеала.

Если известно, что в массивах нет дублирующихся элементов (в одном массиве двух одинаковых), то можно вспомнить про set, который основан на хэш-функции и строится за O(n). Тогда мы строим множество из одного из списков за O(n) (или O(m)), и проидясь по массиву определим, есть ли в множестве дополняющий до 2 элемент. Так как используются хэш-функции доступ будет за O(1).


first_arr = [1, 3, 2, 9, 5, 4, 0, -1, -2, -4, 10, 12, -9]
second_arr = [5, 2, 1, 0, -2, -3, 4, -10, -9, -6, 8, 12, 34, 3, 9, 19]

result = 0
set_from_second_arr = set(second_arr)
for i in first_arr:
    if (2 - i) in set_from_second_arr:
        result += 1

print(result)

Общая сложность примерно O(n + m) (построение множества - O(n), обход списка O(m)).

Если вдруг элементы повторяются, да и такое бывает. Тогда можно вспомнить про Counter, можно его и самому написать, он работает на словарях. Там сложность его построения тоже примерная O(n). Тут отличие от предыдущего алгоритма только в том, что мы прибавлять будем не 1 к результату, а количество повторений подходящего нам дополняющего числа.

from collections import Counter

first_arr = [1, 3, 2, 9, 5, 4, 0, -1, -2, -4, 10, 12, 12, 12, -9]
second_arr = [5, 2, 1, 1, 0, -2, -2, -2, -3, 4, -10, -10, -10, -9, -6, 8, 12, 34, 3, 9, 19]

result = 0
dictionary_from_second_arr = Counter(second_arr)
for i in first_arr:
    if (2 - i) in dictionary_from_second_arr:
        result += dictionary_from_second_arr[(2 - i)]

print(result)

Ну примерно так, много разных подходов к решению задач.

1
1

В большинстве 27-х задач есть простое решение перебором циклом в цикле. И, как правило, надо найти "лайфхак", как все сделать за один проход цикла: и данные считать, и запомнить ограниченное количество входных данных, из которых в конце и сварганить ответ. Конкретная реализация зависит от задачи. Трудно поверить в вашу формулировку задания: "суммы чисел которых равна 2". Может "кратна 2"? Сложностей при подготовке не надо, наверное, придумывать. Максимум - создать служебный массив, делать с ним pop и append(или как в вашем языке это), научиться получать цифры попарно. Сортировку я, вроде, видел только в каких-то давнишних заданиях.

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