만약 당신이 인코딩 커뮤니티에 한동안 머물렀다면, 당신은 아마도'대 O'와/또는'시간 복잡성'이라는 단어를 들은 적이 있을 것이다.적어도 이런 용어의 의미를 모르면 사기꾼 증후군이나 무능한 느낌이 들 수 있다.본고에서 나는 시간의 복잡도와 함수의 대O를 어떻게 계산하는지 소개할 것이다.비록 이런 계산은 어느 정도 보잘것없지만 개념과 그 작업 원리를 이해하는 것은 매우 유익할 수 있다.시작합시다.

포인트가 뭐예요?

시간 복잡도는 함수 완성에 필요한 시간량을 계산하는 데 쓰인다.간단한'모든 숫자의 합'함수를 예로 들자.사용자가 한 숫자를 전송합니다. 1부터 우리는 모든 숫자를 전송된 숫자에 도달할 때까지 추가합니다.예:addUpTo(5)
반환됨1+2+3+4+5 = 15.우리는 이 함수를 정의할 수 있는 많은 방법이 있지만, 어떤 방법은 다른 방법보다 빠르다.계산 함수로 정의된 대O를 통해 우리는 두 가지 알고리즘의 시간 복잡도를 비교하여 어떤 알고리즘이 더 빠른지 제시할 수 있다.

무엇이 큰 O 기호입니까?

대O가 연이어 나타나는 흔한 결과는

O(1)

O(대수(n)

O(n)

O(nlog(n))

O(n^2)

참조 번호: https://cooervo.github.io/Algorithms-DataStructures-BigONotation/
가장 빠른 것은 O(1)(정상 운행 시간)이고, 가장 긴 것은 O(n^2)이다.본문에서 우리는 단지 소개할 것이다

O(1)

O(n)

O(n^2)

파악하기 쉬우니까.이 기호들은 입력이 증가함에 따라 함수가 실행될 수 있는 속도를 나타낸다.예를 들자.n이 커질 때, 그 시간의 복잡도에 따라 이 함수는 더 긴 계산 시간이 필요하거나 필요하지 않을 수도 있다.만약 우리의 알고리즘의 큰 O가 O(n)라면, 실행할 때 선형으로 증가할 것이다.예를 들어 addUpTo(n) 은 addUpTo(100000) 보다 운행 시간이 훨씬 길다.그러나 만약에 우리의 O=O(1)라면, 그것은 n의 크기에 영향을 받지 않고 항정적으로 운행할 때로 여겨진다.

우리는 어떻게 계산합니까?

우리는 계산 알고리즘에 사용되는 간단한 지령수를 통해 알고리즘의 큰 O를 계산할 수 있다.이 두 가지 다른 알고리즘을 addUpTo(n) 함수에 사용합니다.

function addUpToLong(n) {
    let total = 0;
    for (let i = 1; i<=n; i++ ) {
        total += i
    }
    return total
}

function addUpToShort(n) {
    return n * (n + 1) / 2
}

이 두 가지 알고리즘은 같은 결과를 출력하지만, 주의하십시오. 나는 이미 하나의 길이와 하나의 짧은 이름을 명명했습니다.이것은 긴 함수의 운행 시간이 짧은 함수보다 길기 때문이다.먼저 긴 함수의 모든 간단한 지령을 추가합시다.
초기화, 조작, 비교, 반환은 모두 일정한 운행일 때이기 때문에 O(1).이 경우 모든 상수 표현식은 다음과 같습니다.addUpTo(5) let total = 0 let i = 1현재 우리는 3개의 상수가 있는데, 이것은 지금까지의 대O=O(3)
언제든지 하나의 순환이 목록에서 교체되거나 0에서 n으로 점차적으로 증가하면 우리는 이 O(n)가 실행될 때를 고려한다.숫자나 목록이 커지면서 알고리즘이 완성되는 데 걸리는 시간이 동시에 늘어난다는 뜻이다.이런 상황에서 운행할 때 n에 의존한다. 우리의 예시에서 우리는 return total 순환이 있기 때문에 통상적으로 상수인 간단한 표현식마다 n번을 다시 나타낸다. 초기 표현식for을 제외하고는 우리가 몇 번을 순환하든지 간에 그것은 한 번만 운행하기 때문이다.모든 O(n) 표현식은 다음과 같습니다.let i = 1 i<=n i++ total += 1과i++는 모두 두 개의 표현식으로 계산된다. 왜냐하면 우리는 두 개의 연산을 동시에 하기 때문이다.초기화 및 증가분따라서 이 알고리즘의 큰 O 계산은 다음과 같다.

지령을 세어 볼 필요가 있습니까?

여기 간단한 답은 부정적입니다. 하느님께 감사드립니다!우리의 모든 알고리즘을 계산하는 모든 표현식이 얼마나 무미건조한지대O와 시간의 복잡도를 계산하는 정확한 방법은 사실상 전체적인 추세를 식별하는 것이지 특정 수량의 지령이 아니다.
n이 무한대에 이르면 상수 같은 작은 것은 중요하지 않게 변한다.예를 들어 만약에 우리가addUpToLong(99999999)을 호출한다면total += 1과+3 중5은 사실상 중요하지 않다. 왜냐하면 그것은 변하지 않기 때문에 여전히 선형의 전체적인 추세이기 때문이다.따라서 우리는 O(5n+3)를 O(n)로 간소화할 수 있다.한 마디로 하면, O(3)는 항상 상수이기 때문에 O(1)로 간소화된다.가장 중요한 것은 우리가 예시에서 보듯이 자질구레한 계산을 할 필요가 없다는 것을 의미한다.우리는 간단한 일별을 통해 우리의 알고리즘이 어떻게 작동하는지 식별할 수 있다.
n에 의존하는 순환이 없으면 운행 시간은 O(1)입니다. n에 의존하는 단일 순환이 있으면 운행 시간은 O(n)이고, n에 의존하는 플러그인 순환이 있으면 운행 시간은 O(n^2)입니다.O(n^2)는 다음과 같습니다.

function printAllPairs(n) {
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            console.log(i, j)
        }
    }
}

이게 무슨 소용이 있습니까?

만약 당신이 대형 데이터베이스를 사용한다면, 알고리즘의 시간 복잡도를 신속하게 식별할 수 있는 것은 매우 유익할 것이다.나의 예에서, 그것은 보잘것없어 보일 수도 있다.함수가 1초가 아니라 1초가 걸릴지 누가 신경 쓰겠는가.25초 맞나요?그러면 만약에 우리가 알고리즘을 작성하고 있는데 그 중에서 n은 대규모 데이터베이스에서 나온 수백만 개의 숫자와 같으면 어떻게 해야 합니까?이 운행들은 몇 분, 심지어 몇 시간 동안 운행해야 할 것 같다.어떤 경우 학습은 빅데이터 프로젝트의 효율을 최대한 높이면 생명을 구할 수 있다.
제 블로그를 읽어 주셔서 감사합니다.나는 이 예들이 당신에게 유용하고 일관되기를 바랍니다.이 함수로 내 리포를 끌어당기고 실행을 보려면 임의로 리포를 복제해서 실행하십시오. https://github.com/Aaidenplays/data-structures-and-algorithms-2