сложность по времени несортированный массив обратного отслеживания

Question

поэтому у меня есть назначение, где есть этот метод:

publi c int backtrackingSearch (int [] arr, int x, int fd, int bk, Stack myStack), который получает несортированный массив целых чисел arr и ищет индекс первого вхождения значения x с добавленным свойством, которое после каждого fd много шагов поиска, возвращает bk много шагов назад. Алгоритм останавливается, если находит нужный индекс или достигает массива.

Теперь меня спрашивают о сложности времени при вызове функции с (A, x, ?1, ?2) - для ?. ?????ℎ> ?1> ?2 ≥ 0.

Мне действительно трудно анализировать сложность времени здесь

Answer 1

Хорошо, давайте попробуем найти сложность времени, не пытаясь найти функцию времени выполнения. Чтобы сделать это, мы должны рассмотреть наихудший случай. В этом примере наихудший случай, когда x не существует в массиве. Таким образом, программа будет перебирать весь массив.

Но программа также должна возвращаться на каждые n1 шагов вперед, что замедляет процесс. Каждый раз, когда мы пытаемся проверить новые элементы, мы также возвращаем n2 элемента назад, туда, где нет новых элементов для проверки.

Итак, вопрос в том, насколько эти дополнительные «правила» влияют наши оригинальные n шагов по всему массиву (когда n размер массива)? Мы тратим дополнительные n шагов для каждого элемента? - приводя к сложности O (n²). Или это линейно? - это означает, что наши исходные n шагов только умножаются или добавляются к постоянным числам, которые не зависят от размера массива.

Ну, дополнительные шаги зависят только от значений n1 и n2, верно ? Если размер массива удвоится, мы ожидаем, что время выполнения также удвоится. Поэтому, когда размер увеличивается, время выполнения должно увеличиваться линейно.

Следовательно, временная сложность этого метода O (n) - линейная.