Big-O цикла над словарем

Question

Меня интересует сложность цикла big-O в одном и том же словаре дважды, а затем цикл по длине определенного ключа в словаре, как показано в псевдокоде.Что такое Big-O для каждого цикла, и каким будет окончательный Big-O?

Я попытался посмотреть на другие потоки Big-O здесь, но они либо сбивают меня с толку из-за моегоограниченное знание big-O или не так, как в конкретном случае, как то, что я ищу.

Спасибо

dictionary = A dictionary with 100 keys and corresponding values of 10-20 characters each

for Akey in dictionary:
    do something
    for Bkey in dictionary:
        do something
        for i in range(len(dictionary[Bkey]))
            do something

Answer 1

Для словарей python, основанных на хеш-таблице, наихудший случай нахождения элемента - O (n). Однако средний амортизированный случай равен O (1). Так что если вы делаете цикл для всех элементов, то это O (1) x n -> O (n), если только у вас нет вырожденного случая плохих хеш-кодов, а затем у вас есть O (n ^ 2). Если вы выполняете несколько подобных операций, но число этих операций фиксировано и не зависит от n, это не меняет O.

если вы вложите цикл в другой цикл, вам придется умножить стоимость.

О (п * Const) -> О (п). Теперь вы говорили о том, чтобы сделать что-то с ключами, но не упомянули значения.

Из псевдокода кажется, что вы хотите взять список ключей. Перебор всех ключей - это O (n).