Qual a complexidade temporal desta função?

Este é um exemplo em minhas anotações de aula. Esta função possui complexidade de tempo$O(n \log n)$? Como o pior caso é a função entra em elseramificação e 2 loops aninhados com complexidade de tempo de$\log n$ e $n$, então é $O(n \log n)$. Estou certo?

int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}

A complexidade temporal do algoritmo mencionado é $O(1)$, por causa de $K>100$ você tem uma operação constante (println) e sabe: $j=3,k = 3 \cdot n / 345 \implies 100 = 3\cdot n / 345 \implies n=11500$, meios para $n\ge 11500$ seu algoritmo tem um tempo de execução constante (também outra parte é constante, porque apenas para $n<11500$ será chamado).

Por ser mais claro, dê uma olhada nesta questão.

EDIT: Como apontado por Saeed Amiri, este é realmente $O(1)$, já que para grandes assintoticamente grandes $n$, o elseramo não é realmente ocupado; a ifpeça é executada, que é um tempo trivialmente constante. O restante desta resposta, que deixo para referência, estaria correto se, por exemplo, a condição fosse k < 100. Desculpe pela confusão.

A complexidade do tempo será essencialmente da ordem do número de vezes que $k$é incrementado no forloop aninhado . Há algumas coisas extras acontecendo, mas se você pensar sobre isso, é só brincar com fatores constantes. Quantas vezes$k$ ser incrementado?

Quando $i = 1$, $k$é incrementado uma vez. Quando$i = 2$, $k$é incrementado duas vezes adicionais. Quando$i = x$, $k$ é incrementado $x$tempos adicionais. Vamos agora assumir que$n = 2^m + 1$. Então a última iteração do loop interno fará com kque seja incrementada$2^m$ vezes.

$k$ é incrementado um total geral de $1 + 2 + ... + 2^m$ vezes ou $2^{(m+1)} - 1$vezes. Lembre-se de que `$n = 2^m + 1$. assim$n - 1 = 2^m$e nós temos isso $k$ é incrementado $2(n - 1) - 1$ vezes no total.

$k$ é incrementado um número de vezes linear em $n$; então isso é tudo$O(n)$.

Embora os comentários sobre os ramos if / else estejam todos corretos, eu diria que a resposta é O (log n). A razão é que

System.out.println("k: " + k);

envolve a conversão de um número inteiro em saída de string, e este será O (log n) no caso geral (apenas para imprimir cada dígito, mesmo que uma tabela de pesquisa tenha sido usada).

Não tenho certeza se isso foi uma parte complicada da pergunta ou não ...

Vamos ver:

int j = 3; leva tempo constante O (1).

int k = j * n / 345toma alguma função de tempo do logaritmo das variáveis j e n

if (k > 100) leva tempo constante O (1).

System.out.println("k: " + k);assume a função de tempo do logaritmo de k

for (int i=1; i<n; i*=2)toma a função de tempo do logaritmo de n , Θ (log (n)) para ser exata, porque se t é o número de iterações desse loop for, o valor de i pode ser expresso como: i = 2 ^t-1 , se t = 1 na primeira iteração, para que o loop continue enquanto 2 ^t-1 <n , onde n não está sendo alterado.

No cálculo, se 2 ^t-1 <n então t-1 <log ₂ (n)

E se t-1 <log ₂ (n) então t <log ₂ (n) +1

E se em cada iteração, t é incrementado em 1, podemos ver que esse loop for realmente leva Θ (log (n)), se a complexidade do tempo de execução do código dentro do loop for for constante, ou seja, O (1) claro!

Dentro deste loop for, existe outro loop for:

for (int j=0; j<i; j++) k++;

Vamos analisar isso:

k++; leva tempo constante, ou seja, tempo O (1).

Portanto, é interessante analisar a complexidade do tempo de execução do loop for interno.

Vamos ver:

De acordo com o código desse loop for interno, parece que existem i iterações nesse loop for interno, portanto, o tempo de execução é Θ (i) , não apenas O (i) , porque não quebra no meio, mas lembre-se de que i <n , por causa do loop for externo, portanto, embora no início seja necessário 1 iteração quando i = 1 , 2 iterações quando i = 2 , 4 iterações quando i = 4 , 8 iterações quando i = 4 , 8 iterações quando i = 8 . .. e etc, porque eu dobra-se no final do loop for externo na linha i * = 2 , portanto, no total, a execução é 1 + 2 + 4 + 8 + ... iterações, mas até i≥nportanto, o número máximo possível de iterações nesse loop for interno é quando i = n-1 em termos de pior caso; portanto, na última execução do loop for interno, ele executou n-1 iterações, portanto, antes de executar ( n-1) / 2 iterações e antes da execução (n-1) / 4 iterações e antes da execução (n-1) / 8 iterações ... portanto, no total, a execução foi:

n-1 + (n-1) / 2 + (n-1) / 4 + (n-1) / 8 ... = (n-1) (1 + 1/2 + 1/4 + 1/8 ...) = (n-1) (2) = 2n-2 = Θ (n)

Lembre-se de que 1 + 1/2 + 1/4 + 1/8 ... = 2 é uma soma bem conhecida da sequência geométrica.

Lembre-se de que o loop for externo leva Θ (log (n))

E o loop for interno leva Θ (n).

E a complexidade do tempo de execução do loop for interno para o loop é a complexidade do tempo de execução do loop for externo multiplicada pela complexidade do tempo de execução do loop for interno, portanto, leva Θ (nlogn) o tempo de execução.

Portanto, em resumo, o tempo de execução dessa função é Θ (nlogn) .

Espero que isso responda bem à sua pergunta e ensine bem como analisar a complexidade do tempo de execução de algoritmos e funções.