Блог

Главная - Вопросы по программированию - Структуры данных и алгоритмы Объяснение оптимального решения

Структуры данных и алгоритмы Объяснение оптимального решения

#algorithm #data-structures

#алгоритм #структуры данных

Вопрос:

в настоящее время я прохожу курс ds amp; a udemy, поскольку готовлюсь к интенсивному набору этой предстоящей осенью. я наткнулся на проблему, которая подсказала примерно следующее:

«Учитывая массивы списков, выясните, какое целое число отсутствует во втором массиве списков, которое присутствовало в первом массиве списков»

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

Вот несколько решений:

 def finderBasic(list1,list2):

    list1.sort()
    list2.sort()
    
    for i in range(len(list1)):
        if list1[i] != list2[i]:
            return list1[i]

def finderOptimal(list1,list2):

    d = collections.defaultdict(int)

    for num in list2:
        d[num] = 1
    
    for num in list1:
        if d[num] == 0:
            return num
        else:
            d[num] -= 1

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

Комментарии:

1. Обе реализации неверны, если вы не ограничите входные данные. Второй сбой при [1, 1, 2], [1, 1]. Первый сбой при [1], [0, 1]. Второй вариант особенно плох, потому что он добавляет код, который выглядит так, как будто предназначен для работы с дубликатами.

2. set(list1) - set(list2) дает все целые числа, которые находятся в первом списке, которые не отображаются во втором списке.

3. На самом деле, первое решение завершается неудачей list1=[1, 2, 3]; list2=[1, 2] с исключением индекса.

Ответ №1:

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

Однако тяжелая операция здесь — сортировка, поскольку она занимает примерно n * log (n) времени, что больше, чем O (n). Это означает, что даже если вы дважды запустите цикл for во 2-м решении, это все равно будет намного лучше, чем сортировка один раз.

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

См.:https://wiki .python.org/moin/TimeComplexity

Базовое решение может быть лучше для читателя, поскольку оно очень простое и прямолинейное, однако оно более сложное.

Ответ №2:

Отказ от ответственности: я не знаком с Python.

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

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

Более простое не всегда означает наиболее эффективное. И наоборот, эффективное часто трудно понять.