데이터 구조의 빅오 표기법: 알아야 할 모든 것

데이터 구조의 Big O 표기법은 알고리즘의 효율성, 입력이 증가함에 따라 함수를 실행하는 데 걸리는 시간, 함수가 얼마나 잘 확장되는지를 결정하는 데 사용됩니다. 이 효율성을 측정하는 것은 공간 복잡도와 시간 복잡도의 두 부분으로 나눌 수 있습니다.

Big O 표기법은 인수가 특정 값이나 무한대로 기울어지는 경향이 있을 때 모든 기능의 제한 요소로 작용하는 수학적 표기법을 나타냅니다. Edmund Landau, Paul Bachmann 등이 발명한 수학적 표기법의 범주에 속합니다. 따라서 일괄적으로 Bachmann-Landau 표기법 또는 점근 표기법이라고 합니다.

수학적 추론에 따라 f(n) 및 g(n) 의 두 함수 는 제한되지 않은 양수 또는 실수 집합에 대해 정의됩니다. 여기서 g(n) 은 n의 모든 큰 값에 대해 엄격하게 양수입니다. 다음과 같은 방식으로 작성할 수 있습니다.

f(n) = O(g(n)) 여기서 n은 무한대 (n → ∞) 가 되는 경향이 있습니다.

그러나 여기서 무한대에 대한 n의 가정은 배타적으로 정의되지 않으므로 위의 식은 다음과 같이 쓸 수 있습니다.

f(n) = O(g(n))

여기서 f와 g는 양의 정수에서 음이 아닌 실수로 시작하는 필수 함수입니다.

따라서 큰 n 값은 Big O 점근선으로 표시됩니다.

데이터 구조에서 Big O 표기법 의 속성

데이터 구조 의 Big O 알고리즘은 몇 가지 필수 속성을 가지고 있습니다. Big O Notation의 필수 속성은 다음과 같습니다.

• 합산 기능:
  f(n) = f 1 (n) + f 2 (n) + — + f m (n) 및 f i (n)≤ f i +1(n) ∀ i=1, 2,–, m인 경우
  그런 다음 O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• 대수 함수:
  f(n) = logan 및 g(n) = logbn인 경우
  O(f(n))=O(g(n))
• 상수 곱셈:
  f(n) = cg(n)이면 O(f(n)) = O(g(n))입니다. 여기서 c는 0이 아닌 상수입니다.
• 다항식 함수:
  f(n) = a0 + a1.n + a2.n2 + — + am.nm이면,
  O(f(n)) = O(nm).

세계 최고의 대학에서 온라인으로 소프트웨어 개발 과정 을 배우십시오 . 이그 제 큐 티브 PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 획득하여 경력을 빠르게 추적하십시오.

인기 있는 소프트웨어 엔지니어링 과정 살펴보기

여기서 Big O를 처리하는 동안 모든 단일 로그 함수는 유사하게 증가합니다.

알고리즘의 런타임 분석에서 Big O 표기법의 중요성

알고리즘의 최악의 경우 실행 시간의 복잡성은 특히 알고리즘의 성능을 분석하는 경우 비교 및 ​​계산에 사용됩니다. 상수 실행 시간으로 표시된 O(1)의 순서는 알고리즘의 가장 빠른 실행 시간입니다. 알고리즘에 걸리는 시간은 다양한 입력 크기에 대해 동일합니다. 알고리즘의 이상적인 실행 시간은 일정한 실행 시간이며 알고리즘의 실행 시간이 n의 입력 크기에 의존하기 때문에 매우 드물게 달성된다는 점에 유의하는 것이 중요합니다.

예를 들어:

위에서 언급했듯이 알고리즘의 런타임 성능은 주로 n의 입력 크기에 따라 달라집니다. 다양한 크기의 n에 대한 알고리즘의 런타임 분석을 수행하기 위해 몇 가지 수학적 예를 통해 이 사실을 설명하겠습니다.

• n = 20
  로그(20) = 2.996;
  20 = 20;
  20 로그(20) = 59.9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2.432902 + 18 18 ;
• n = 10
  로그(10) = 1;
  10 = 10;
  10 로그(10) = 10;
  10 2 = 100;
  2 10 = 1024;
  10! = 3628800;

알고리즘의 런타임 성능도 유사하게 계산됩니다.

다음은 런타임 분석의 몇 가지 다른 알고리즘 예제입니다.

• 선형 검색의 경우 런타임 복잡도는 O(n)입니다.
• 이진 검색의 경우 런타임 복잡도는 O(log n)입니다.
• 선택 정렬, 버블 정렬, 버킷 정렬, 삽입 정렬의 경우 런타임 복잡도는 O(n^c)입니다.
• 하노이 타워와 같은 지수 알고리즘의 경우 런타임 복잡도는 O(c^n)입니다.
• Merge SortSort 및 Heap Sort의 경우 런타임 복잡도는 O(n log n)입니다.

Big O는 공간 복잡성을 어떻게 분석합니까?

알고리즘에 대한 공간 및 런타임 복잡성을 결정하는 것은 필수적인 단계입니다. 이는 알고리즘의 공간 복잡도 분석을 통해 알고리즘의 런타임 성능과 알고리즘이 차지하는 메모리 공간을 분석하여 알고리즘이 수행하는 실행 시간을 결정할 수 있기 때문입니다. 따라서 알고리즘의 공간 복잡도를 측정하려면 알고리즘의 최악의 공간 복잡도 성능을 비교해야 합니다.

알고리즘의 공간 복잡도를 결정하려면 다음 두 가지 작업을 따라야 합니다.

작업 1: 특정 알고리즘에 대한 프로그램을 구현하는 것이 중요합니다.

작업 2: 각 항목이 보유할 메모리를 결정하려면 입력 n의 크기를 아는 것이 필수적입니다.

알고리즘의 공간 복잡도를 계산하기 전에 이 두 가지 필수 작업을 수행해야 합니다.

공간 복잡도 알고리즘의 예

공간 복잡도가 있는 알고리즘의 많은 예가 있으며, 이러한 유형의 알고리즘에 대한 더 나은 이해를 위해 그 중 일부가 아래에 언급되어 있습니다.

• 버블 정렬, 선형 검색, 선택 정렬, 삽입 정렬, 힙 정렬 및 이진 검색의 경우 공간 복잡도는 O(1) 입니다.
• 기수 정렬 의 경우 공간 복잡도는 O(n+k) 입니다.
• 빠른 SortSort 의 경우 공간 복잡도는 O(n) 입니다.
• 병합 정렬 의 경우 공간 복잡도는 O(log n) 입니다.

C에서 Big O 표기법의 예

Big O 표기법은 알고리즘의 복잡성이나 성능을 결정하기 위해 컴퓨터 과학에서 주로 사용되는 사실입니다. 이 표기법은 입력 데이터의 범위가 커질 때 메모리 공간의 증가 또는 실행 시간 요구 사항을 기반으로 알고리즘의 동작을 분류하는 기능을 제공합니다. 실제 메모리 사용량이나 실행 시간을 예측하기 위한 것이 아니라 알고리즘을 비교한 다음 작업에 가장 적합한 알고리즘을 선택하기 위해 설계되었습니다. 특정 언어는 아니지만 C로도 구현됩니다.

아래에서 알고리즘의 최악의 경우 복잡성(Big O 표기법)이 계산된 C에서 선택 정렬 알고리즘을 찾을 수 있습니다.

for(int i=0; i<n; i++)

{

정수 분 = 나;

for(int j=i; j<n; j++)

{

if(배열[j]<배열[최소])

최소 = j;

}

정수 임시 = 배열[i];

배열[i] = 배열[최소];

배열[최소] = 온도;

}

알고리즘을 분석하려면:

• for 외부 루프의 범위는 i < n 이며 루프의 순서가 O(n)임을 나타냅니다.
• 다음으로 내부 for 루프의 경우 j < n이므로 O(n)이기도 함을 식별할 수 있습니다.
• 상수 c에 대해 평균 효율이 n/2인 경우에도 상수는 무시됩니다. 따라서 차수는 O(n)입니다.
• 내부 루프와 외부 루프의 순서를 곱한 후 달성된 런타임 복잡도는 O(n^2)입니다.

C의 다른 알고리즘은 복잡도가 유사하게 쉽게 분석되고 결정될 수 있는 쉽게 구현될 수 있습니다.

Big O 표기법의 사용

Big O 표기법이 적용되는 두 가지 주요 영역이 있습니다.

• 수학 : Big O 표기법은 특히 점근 확장 또는 잘린 테일러 급수의 경우에 유한 급수가 함수에 근접하는 방법을 설명하기 위해 수학 분야에서 매우 일반적으로 사용됩니다.
• 컴퓨터 과학: 빅오 표기법이 알고리즘 분석에 유용하기 때문에 컴퓨터 과학 분야에서 주로 사용되는 것은 잘 알려진 사실입니다.

그러나 두 응용 모두 에서 O (·) 안에 나타나는 함수 g ( x ) 는 하위 항과 상수 인수가 생략되는 경우 가장 단순한 것으로 선택되는 경우가 많습니다.

이 표기법에는 형식적으로 가깝지만 상대적으로 다른 두 가지 다른 용도가 있습니다. 그들은:-

• 무한 점근법
• 무한 점근선.

그러나 이러한 구분은 원칙적으로 적용되지 않으며 두 경우 모두 "Big O"에 대한 형식 정의가 정확히 동일합니다. 유일한 차이점은 함수의 인수에 대한 제한입니다.

소프트웨어 개발과 관련된 인기 기사 읽기

결론

결론적으로 빅데이터는 데이터 구조에서 필수적인 역할을 하고 있으며, 빅오 표기법에 대한 깊이 있고 포괄적인 지식을 보유하는 것은 훌륭한 기술 세트라고 할 수 있습니다. 직업 부문에서 수요가 높으며 잠재적으로 경력 경로에 대한 훌륭한 선택이 될 수 있습니다. upGrad의 빅 데이터 고급 인증 프로그램은 경력을 향상시키는 데 필요한 수단을 제공합니다. PySpark를 사용한 데이터 처리, 데이터 웨어하우징, MapReduce, AWS 클라우드에서의 빅 데이터 처리, 실시간 처리 등과 같은 최고의 전문 기술을 소개합니다.