빅오 표기법 예제

가장 간단한 예제인 T(n)와 O(1)로 시작해 보겠습니다. Big O 표기는 알고리즘의 시간 복잡성(최악의 경우 성능)을 설명하거나 계산하는 데 사용됩니다. 이 게시물은 Big O 표기법의 구체적인 예를 보여줍니다. Big O 표기법을 사용하면 알고리즘을 실행하는 데 걸리는 시간이 얼마나 오래 걸릴지 확인할 수 있습니다. 이를 통해 코드 의 일부가 어떻게 확장되는지 이해할 수 있습니다. 알고리즘 효율성을 측정합니다. 런타임 분석의 알고리즘 예: 최악의 시나리오에서 이러한 모든 유형의 알고리즘의 예 중 일부는 아래에 설명되어 있습니다. 가장 중요한 용어는 명시적으로 작성된 다음 가장 중요하지 않은 용어는 하나의 큰 O 용어로 요약됩니다. 예를 들어, 지수 계열과 x가 작을 때 유효한 두 개의 식을 생각해 보십시오. 다른 예에서는 일부 알고리즘의 경우 정확한 단계 수가 (T(n)=5n^{2}+27n+1005라고 가정합니다. n이 작으면 1 또는 2라고 하면 상수 1005가 함수의 지배적인 부분인 것 같습니다. 그러나 n이 커지면 (n^{2})라는 용어가 가장 중요해집니다.

실제로 n이 실제로 크면 최종 결과를 결정하는 데 있어 다른 두 용어가 중요하지 않게 됩니다. 다시 말하지만 n이 커지면 (T(n)를 근사화하기 위해 다른 용어를 무시하고 (5n^{2})에 집중할 수 있습니다. 또한 n이 커지면 계수 (5)가 중요하지 않게 됩니다. 우리는 함수 (T(n))의 크기 순이 (f(n)=n^{2})이거나 단순히 (O(n^{2})입니다.라고 말할 것입니다. for 루프를 포함하는 다음 C 예제를 살펴보겠습니다. 정확한 작업 수는 (T(n)) 함수의 가장 지배적인 부분을 결정하는 것만큼 중요하지 않은 것으로 나타났습니다. 즉, 문제가 커질수록 (T(n)) 함수의 일부가 나머지 함수를 압도하는 경향이 있습니다. 이 지배적 인 용어는 결국 비교에 사용됩니다. 크기 함수의 순서는 n값이 증가함에 따라 가장 빠르게 증가하는 (T(n))의 부분을 설명합니다. 크기의 순서는 종종 Big-O 표기문서(«주문»)라고 하며 (O(f(n))로 작성됩니다.

계산의 실제 단계 수에 대한 유용한 근사치를 제공합니다. 함수 (f(n))는 원래 (T(n)의 지배적인 부분을 간단하게 표현합니다. 단위를 변경하면 결과 알고리즘의 순서에 영향을 줄 수도 있습니다. 단위 를 변경하는 것은 나타나는 위치에 상수를 곱하는 것과 같습니다. 예를 들어 알고리즘이 n2의 순서로 실행되는 경우 n을 cn으로 대체하는 것은 알고리즘이 c2n2 의 순서로 실행되고 큰 O 표기는 상수 c2를 무시합니다. 이것은 c2n2 = O(n2)로 기록될 수 있다. 그러나 알고리즘이 2n 의 순서로 실행되는 경우 n을 cn으로 대체하면 2cn = (2c)n이 됩니다. 이것은 일반적으로 2n과 동일하지 않습니다. 변수를 변경하면 결과 알고리즘의 순서에도 영향을 줄 수 있습니다. 예를 들어 알고리즘의 런타임이 입력 번호 x의 자릿수 n으로 측정될 때 O(n)인 경우 n = O(log x)가 입력 번호 x 자체의 함수로 측정될 때 실행 시간은 O(log x)입니다. 우리는 로그 내의 n의 힘을 무시할 수 있습니다. 집합 O(log n)는 O(로그(nc))와 정확히 동일합니다.

로그(log)는 상수 계수(log(nc) = c log n)에 의해서만 다르므로 큰 O 표기는 이를 무시합니다. 마찬가지로 상수 베이스가 다른 로그는 동일합니다. 반면에 다른 베이스를 가진 지수가 같은 순서가 아닙니다. 예를 들어 2n 및 3n은 동일한 순서가 아닙니다. Little-o는 여러 산술 연산을 존중합니다. 예를 들어 일반적으로 최적의 메모리 사용과 런타임 성능 간에는 장단점이 있습니다. 일반적으로 알고리즘의 경우, 공간 효율성과 시간 효율은 두 개의 반대쪽 끝에 도달하고 그 사이의 각 지점은 특정 시간과 공간 효율을 가시다. 따라서 시간 효율성이 높아지수록 공간 효율성이 낮아지고 그 반대의 경우도 마찬가지입니다.