Какая сложность у подобного алгоритма?

Рейтинг: 0Ответов: 1Опубликовано: 02.06.2023

Правильно ли я понимаю, что:

for i in range(len(abc)):
    if i in zxc:   

по сути имеет сложность O(n^2) так как мы имеем цикл сложностью O(n) и внутри него используем in, который так же имеет сложность O(n)?

Ответы

▲ 3Принят

Цикл for i in range(len(abc)) имеет сложность O(n), n - длина списка abc.

Операция if i in zxc, имеет сложность O(m), где m - длина списка zxc.

Общая сложность будет O(n * m).