Означает ли один цикл for временную сложность n в этом случае? - PullRequest
Новая
       21

Означает ли один цикл for временную сложность n в этом случае?

1 голос
/ 21 мая 2019

Итак, я столкнулся с этой проблемой в ежедневной задаче кодирования и разработал два решения.Тем не менее, я не уверен, если один лучше, чем другой, с точки зрения сложности времени (Big O). 

# Given a list of numbers and a number k, 
# return whether any two numbers from the list add up to k.
#
# For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
#
# Bonus: Can you do this in one pass?
# The above part seemed to denote this can be done in O(n).


def can_get_value(lst=[11, 15, 3, 7], k=17):
    for x in lst:
        for y in lst:
            if x+y == k:
                return True
    return False


def optimized_can_get_value(lst=[10, 15, 3, 7], k=17):
    temp = lst
    for x in lst:
        if k-x in temp:
            return True
        else:
            return False


def main():
    print(can_get_value())
    print(optimized_can_get_value())


if __name__ == "__main__":
    main()

Я думаю, что второе лучше, чем первый, так как он имеет один для цикла, но я 'Я не уверен, что это O (n), так как я все еще работаю с двумя списками.Другое решение, которое я имел в виду, что, по-видимому, было решением O (n), было использование Python-эквивалента «Java HashSets».Буду признателен за подтверждение и объяснение, почему / почему нет, это O (n).

Ответы [ 2 ]

2 голосов
/ 21 мая 2019

Первое решение can_get_value() - учебник O(n^2).Вы знаете это.

Второе решение также.Это потому, что elm in list имеет O(n) сложность , и вы выполняете его n раз.O(n) * O(n) = O(n^2).

Решение O(n) здесь заключается в преобразовании из list в set (или, что ж, хеш-таблицы любого типа - dict также будет работать).Следующий код проходит по списку ровно дважды, это O(n): 

def can_get_value(lst, k):
    st = set(lst)      # make a hashtable (set) where each key is the same as its value
    for x in st:       # this executes n times --> O(n)
        if k-x in st:  # unlike for lists, `in` is O(1) for hashtables
            return True
    return False

Таким образом, в большинстве случаев это O(n) * O(1) = O(n).

1 голос
/ 21 мая 2019

Чтобы проанализировать асимптотическое время выполнения вашего кода, вам также необходимо знать время выполнения каждой из функций, которые вы вызываете. Обычно мы думаем об арифметических выражениях, таких как сложение, как о постоянном времени (O (1)), поэтому ваша первая функция имеет два цикла for для элементов n, а тело цикла занимает только постоянное время, выходя в O (n * n *). 1) = O (n ^ 2).

Вторая функция имеет только одну функцию for loop, но проверка членства для списка является функцией O (n) по длине списка, поэтому у вас все еще есть O (n * n) = O (n ^ 2). Последний вариант все еще может быть быстрее (возможно, Python оптимизировал код для проверки членства в списке), но он не будет асимптотически быстрее (время выполнения по-прежнему увеличивается в квадрате в n).

EDIT - как указал @Mark_Meyer, ваша вторая функция на самом деле O (1), потому что в ней есть ошибка; извини, я просмотрел это и не заметил. Этот ответ предполагает исправленную версию второй функции, например 

def optimized_can_get_value(lst, k=17):
    for x in lst:
        if k - x in lst:
            return True
    return False

(Примечание. У вас нет значения по умолчанию для вашей функции, которая может быть изменяемой. См. этот вопрос SO о возможных проблемах. Я также удалил временный список, потому что в этом нет необходимости; в любом случае он просто указывал на один и тот же объект списка.)

РЕДАКТИРОВАТЬ 2: для забавы, вот пара из O (n) решений этого (оба используют, что проверка сдерживания для набора является O (1)).

Однострочник, который по-прежнему останавливается, как только найдено решение: 

def get_value_one_liner(lst, k):
    return any(k - x in set(lst) for x in lst)
  • РЕДАКТИРОВАТЬ 3: Я думаю, что это на самом деле O (n ^ 2), потому что мы называем set(lst) для каждого x. Я думаю, что использование выражений присваивания в Python 3.8 может дать нам одну строчку, которая все еще эффективна. У кого-нибудь есть хороший Python <3.8 с одной строкой? </li>

И версия, которая пытается не выполнять дополнительную работу путем создания набора по ходу дела (не уверен, что это на самом деле быстрее на практике, чем создание всего набора в начале; это, вероятно, зависит от фактических входных данных): 

def get_value_early_stop(lst, k):
    values = set()
    for x in lst:
        if x in values:
            return True
        values.add(k - x)
    return False
...