Сложность пространства: инициализация хэш-карты ключами и обновление ее значений отдельно по сравнению с динамическим заполнением пар ключ-значение внутри цикла.

Допустим, у меня есть простая проблема, связанная с возвратом индекса появления всех символов в строке. Я знаю, что вы можете буквально запустить один цикл for и распечатать его, но допустим, мне нужно вернуть его в какой-то структуре данных!

Другие предположения: мы точно знаем, что это строка ASCII. В строке нет повторяющихся символов.

Я мог бы сделать одну из двух вещей.

    • Заранее инициализируйте хэш-карту со всеми возможными 128 ключами и None в качестве значений.

    • Переберите строку и просто обновите словарь/хэш-карту
      , указав индекс в качестве значения ключа.

    • Переберите элементы словаря и удалите те пары ключ-значение, где значение равно None.

      ascii_occurrence = {'a': None, 'b': None, 'c': None ... char#128: None} #Initialize a hashmap with each of the 128 characters as key, and set None to its value.

for charIndex in string:
    ascii_occurrence[string[charIndex]] = charIndex

indexMap = {k: v for k, v in ascii_occurrence.items() if v is not None}

print(indexMap)

    • Инициализируйте ПУСТОЙ хэш-карту без ключей или значений.

    • Переберите строку и создайте пары ключ-значение.

      ascii_occurrence = {}

for charIndex in string:
    ascii_occurrence[string[charIndex]] = charIndex

print(ascii_occurrence)

Я уверен, что временная сложность в обоих случаях равна O(N), но я не уверен в пространственной сложности обоих подходов.

Рассуждая о космических сложностях:

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

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

Верен ли мой аргумент?


python-3.x python hashmap time-complexity space-complexity
person imperialgendarme    schedule 05.08.2018    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Сложность ваших обоих подходов составляет O (N ^ 2), потому что у вас есть индексация на каждой итерации (string[charIndex]). Однако ваш второй подход, как правило, лучше в этом случае. Но вы также можете сделать это более оптимизированным способом (с точки зрения времени выполнения), используя понимание словаря следующим образом:

ascii_occurrence = {charIndex: ind for ind, charIndex in enumerate(string)}

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

Сложность этого фрагмента с точки зрения времени выполнения и памяти, конечно, O(N).

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

ascii_occurrence = dict(enumerate(string))
person kasravnd    schedule 05.08.2018
comment
Спасибо за ваш ответ! Можете ли вы объяснить мне немного подробнее, почему это O (N ^ 2)? Насколько я знаю, вы перебираете строку один раз, а внутри цикла вы устанавливаете значение для ключа, не так ли или получаете элемент в словаре O (1)? - person imperialgendarme; 06.08.2018