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

У меня много проблем с этой проблемой алгоритмов. Я должен найти большой тета-анализ следующего алгоритма:

function example(n):
    int j=n
    for i=0;i<n;i++:
        doSomethingA()
        for k=0;k<=j;k++:
            doSomethingB()
        j/=2

Мой подход состоит в том, чтобы разбить все выполнение алгоритма на две части. Одна часть, где вызываются doSomethingA() и doSomethingB(), а вторая часть после того, как j становится 0, вызывается только doSomethingA() до тех пор, пока программа не остановится.

При таком подходе часть 1 выполняется для итераций Logn внешнего цикла, а часть 2 — для итераций n-logn внешнего цикла.

Количество запусков внутреннего цикла уменьшается вдвое для каждого запуска, поэтому общее количество запусков должно быть 2n-1. Таким образом, время выполнения части 1 должно быть (2n-1)*c, константа. Я не совсем уверен, что это действительно

Для части 2 работа внутри цикла всегда постоянна, и цикл повторяется (n-logn) раз.

Итак, мы имеем ((2n-1)+(n-logn))*c

Я не уверен, что работа, которую я сделал до сих пор, правильна, и я не уверен, как продолжить. Моя интуиция подсказывает мне, что это O(n), но я не уверен, как рационализировать это в большой тета. Помимо этого, возможно, весь мой подход ошибочен. Как я должен атаковать такой вопрос? Если мой подход верен, как мне его завершить?

Спасибо.


algorithm computer-science big-o asymptotic-complexity
person Conor James Thomas Warford Hen    schedule 15.02.2018    source источник
comment
Это Big O без тета :) Также Big O - это просто обозначение (широко используемое в математике): то, что вы анализируете, - это временная сложность.   -  person giorgiga    schedule 15.02.2018
comment
Я в замешательстве. Big-O и Big-Theta — разные понятия, не так ли? Меня попросили найти Биг-Тета, а не Биг-О.   -  person Conor James Thomas Warford Hen    schedule 15.02.2018
comment
Да, О и Тета — разные понятия. Тета — это то же самое, что (О и Омега). Примерно O — это своего рода верхняя граница, Omega — нижняя граница, и, следовательно, Theta — это точно такое же асимптотическое поведение.   -  person Henry    schedule 15.02.2018
comment
Мое плохое: я совершенно забыл, что на самом деле существовало - я думаю, слишком много лет вдали от академических кругов :-)   -  person giorgiga    schedule 15.02.2018
comment
Внутренний цикл будет выполняться по крайней мере один раз во время каждой итерации внешнего цикла (даже когда j достигает 0, он будет выполняться один раз)   -  person Henry    schedule 15.02.2018

Ответы (1)


arrow_upward
1
arrow_downward

Легче исследовать, как часто выполняются doSomethingA и doSomethingB.

Для doSomethingA это явно n раз.

Для doSomethingB мы получаем (n+1) + (n/2+1) + (n/4+1) + ... + 1, так что примерно 2n + n. 2n от n+n/2+n/4+... и n от суммирования единиц.

Все вместе мы получаем O (n), а также Theta (n), поскольку вам нужно как минимум Omega (n), как видно из n раз doSomethingA выполняется.

person Henry    schedule 15.02.2018