@zlodiak

Почему время выполнения на разных машинах отличается?

Я попытался сравнить два алгоритма, которые ищут уникальный элемент в списке. Далее для пропуска всяких проверок, допускается, что список всегда содержит более 3 элементов и элементы могут быть только 1 или 2.

#!/usr/bin/env python3

import timeit

def find_uniq_1(arr):
    ''' итоговая сложность: O(n) | время выполнения: 0.002494273998308927 '''
    a, b = set(arr) #O(len(arr))
    return a if arr.count(a) == 1 else b # O(n)

mock = [1 for x in range(100000)]
mock.extend([ 1, 1, 1, 2, 1, 1 ])
start = timeit.default_timer()
print(find_uniq_1(mock))
stop = timeit.default_timer()
print('Time for find_uniq_1: ', stop - start)  


def find_uniq_2(arr):
    ''' итоговая сложность: O(n) | время выполнения: 0.01582404098007828 '''
    first = arr[0]  # O(1)
    left = []       # O(1)
    right = []      # O(1)

    for n in arr:   # O(n)
        if n == first:
            left.append(n)      # O(1)
        else:
            right.append(n)     # O(1)

    return right[0] if len(left) > 1 else left[0]   # O(1)

mock = [1 for x in range(100000)]
mock.extend([ 1, 1, 1, 2, 1, 1 ])
start = timeit.default_timer()
print(find_uniq_2(mock))
stop = timeit.default_timer()
print('Time for find_uniq_2: ', stop - start)


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

Я понимаю, что многое зависит от железа, но порядок это вполне конкретный показатель. И если у сложности в О-нотации такая большая погрешность, то нужно ли вообще заморачиваться со сложностью алгоритма?
  • Вопрос задан
  • 192 просмотра
Решения вопроса 1
@deliro
Ещё раз, чёрным по белому. Сложность алгоритма НЕ ОТРАЖАЕТ реального времени выполнения. Время может различаться хоть в миллион раз. Сложность ОТРАЖАЕТ характер роста времени/памяти при росте этого твоего N.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
28 мар. 2024, в 18:16
1000 руб./за проект
28 мар. 2024, в 18:15
90000 руб./за проект
28 мар. 2024, в 18:05
5000 руб./за проект