Эффективность времени выполнения цикла для двух сравнений по сравнению с циклом дважды для одного сравнения каждый

Question

Название может показаться запутанным, но что я имею в виду, я покажу в коде:

for x in array {
    if (x == 6)
       print("match")
    if (x == 8)
       print("match")
}

против

for x in array {
    if (x == 6)
       print("match")
}
for x in array {
    if (x == 6)
       print("match")
}

Я бы предположил, что они оба O (2n) или O (n), но я не уверен. Если зацикливание требует больше вычислительной мощности, чем сравнение по какой-то причине, то я был бы неправильным. Спасибо

Answer 1

Время выполнения каждого из этих циклов равно O (n), поскольку вы посещаете каждый из n элементов постоянное число раз (один раз в первом случае, два раза во втором) и выполняете самое большее постоянный объем работы над каждым элементом.

Нотация Big-O измеряет асимптотическое время выполнения фрагмента кода, поэтому, говоря, что оба фрагмента кода выполняются за время O (n), не означает, что для их завершения требуется одинаковое количество времени. Вы должны измерить это на вашей конкретной системе с вашей конкретной настройкой, чтобы увидеть, что быстрее. Я подозреваю, что первая версия будет быстрее, так как она делает только один проход по списку.

При этом я бы с осторожностью попытался оптимизировать код, подобный этому. Сначала стремитесь к ясности, и если вы обнаружите, что это узкое место в производительности, то подумайте о его пересмотре. Скорее всего, если это замедляет всю вашу программу, переключение на другое представление данных, такое как сохранение всего в хэш-таблице или сбалансированное BST, будет быстрее, потому что ожидаемая стоимость проверки наличия элемента составляет O (1 ) или O (log n), соответственно, для этих типов контейнеров.