Q: большой O вложенного цикла while внутри цикла for - PullRequest
Новая
       19

Q: большой O вложенного цикла while внутри цикла for

0 голосов
/ 03 октября 2018

Я реализую подсчет вхождения целого числа от 1 до n в списке n-длины.Условие не позволяет дополнительные структуры данных.Манипулировать только оригинальным списком.Выведите целое число и его число
Например: 

org_arr  = [3, 4, 3, 1]
count_int(org_arr )
for i, item in enumerate(org_arr , 1):
    print(i, '->', abs(item))

output: 

1 -> 1
2 -> 0
3 -> 2
4 -> 1

Ниже приведена моя реализация count_int () 

def count_int(arr):
    for i, check_index in enumerate(arr):
        if check_index > 0:
            arr[i] = 0
            while True:
                next_item = arr[check_index-1]
                if next_item < 0:
                    arr[check_index-1] -= 1
                    break
                elif next_item > 0:                     
                    arr[check_index-1] = -1
                    check_index = next_item
                else:
                    arr[check_index-1] = -1
                    break

count_int () использует отрицательный счет и index = k - 1 для целого числа k (как указано 1 <= k <= n) для достижения цели.После запуска исходный массив <code>org_arr равен [-1, 0, -2, -1]

У меня вопрос к большому O этой функции.Это O (n) или O (n ^ 2)?

В худшем случае для цикла for org_arr [0] требуется n-1 циклов цикла while для установки значения org_arr [1] в org_arr [n-1] в отрицательные счетчики.После этого цикл while не будет вызываться.Следовательно, это (n-1) while-циклов + (n-1) for-циклов.Это будет 2 (n-1).Итак, это O (n), но мой друг говорит, что это O (n ^ 2), потому что внутри цикла for есть вложенный цикл while.

1 Ответ

0 голосов
/ 09 октября 2018

Ваш анализ верен.Во многих случаях вложенный цикл может привести к производительности O (n ^ 2), но в этом случае один и тот же индекс не может быть дважды положительным в цикле while.Это означает, что общее время выполнения цикла while на всех итерациях будет не более n раз постоянной, а n - другой константой, то есть O (n) (поскольку он может проверять до n элементов в одном цикле, но послеэто вернется в постоянное время, если тот же элемент ударил снова).Конечно, он не может работать быстрее, чем O (n), поскольку цикл for касается каждого элемента один раз.

...