착화합 선형 O(n)

오늘날에는 알고리즘 실행 속도와 입력 시간의 차이가 일정하고 복잡해졌습니다. Só que na complexidade linear a diferença é bem 비례 ao tamanho da entrada, ao invés de ser gritante.

Em Big O Notation, 복잡한 선형 é apresentada como O(n). 문자열 매칭 알고리즘은 Boyer-Moore(Galil의 regra를 사용)와 선형으로 복잡하게 구성됩니다.

mas a questão toda não é pegar os algoritmos conhecidos e procurar no Google a complexidade deles e sim enxergar os padrões nesses algoritmos e entender a ponto de flagrar a complexidade no seu código e de outras pessoas. Pergunta a ser feita não é "esse algoritmo é O(n)?"e sim "O porquê desse algoritmo ser O(n)?".

최종 응답자 응답자가 최종 응답자일 때 Big O 표기법을 입력해야 합니다.

복잡한 선형, O(n), 다음 형식의 알고리즘을 시연합니다.

package main

import (
    "fmt"
)

func linear(n int) int {
    total := 0
    for i := 1; i <= n; i++ {
        total++
    }
    return total
}

func main() {
    fmt.Println(linear(10))
}

Aqui temos uma operação apenas e não três como anteriormente, nesse caso é total++ que é o mesmo que: total é igual a total + 1, porém a complexidade é totalmente diferente pois o input também define quantas vezes i será incrementado no for statement . Então quanto maior for o input_(n)_ maior o numero de operações serão feitas em total.

Se no lugar de (i <= n) eu colocasse (i <= 10) seria um tempo constante O(1) mas como o 입력 간섭 no for essa complexidade é O(n).

Se formos olhar cada pedaço e dizer o número de operações:

합계 := 0(Uma operação)

i := 0 (Uma operação)

i++(N개 작동)

총++( N 작업)

Quando for analisar a complexidade do algoritmo não é necessário contar todas as operações, na maioria das vezes você vai acabar percebendo. Nesse caso como temos operações que são relacionadas a N que é o numero de inputs não tem porque nos preocuparmos com as que são constantes pois a parte linear já dominará a notação de complexidade, então se a gente deixar as constantes de lado sobram apenas as O (N).

E se você tiver dois for statement? Tipo assim:

package main

import "fmt"

func elevador(n) {
    for i := 0 ; i < n; i++{
        fmt.Println(i)
    }

    for j := n - 1 ; j >= 0; j--{
        fmt.Println(j)
    }
}

Ainda assim a complexidade será O(n) e não O(2n) porque Big O é sobre o comportamento quando a entrada cresce muuuuito. Lá perto do infinito e além pouco importa se é n ou 2n.

Pode ser que eu esteja batendo na mesma tecla, porém recomendo que leia mesmo as partes que você thinka que já sabe. O maior perigo de aprender é achar que já entendeu e não precisa estudar mais.



Agora temos em perspectiva dois tipos de complexidade a constante em cinza e a linear em azul e agora fica muito óbvio o porque do nome. Repare que dessa vez o input é de 10gb e não 10tb se eu tentasse fazer com um input de 10tb em um algoritmo de complexidade O(n) levaria bem mais tempo. A Linha de O(1) permanece plana não leva nem 1 segundo de runtime, a azul com um input de 10gb já leva 18 segundos.

Eu não to falando pra você ficar contando segundo, isso vai dependser do seu cenário, mas se você olhar o quanto as linhas já se distanciaram é bastante e como diz o ditado "de grão em grão a galinha enche o papo".