시간 복잡도(Time Complexity)

※ 이 글은 chatGPT를 기반으로 작성한 글입니다.

 

① 시간 복잡도(time complexity)는 알고리즘의 수행 시간이 입력 크기에 따라 어떻게 증가하는지를 분석하는 데 사용되는 개념이다.

② 알고리즘의 시간 복잡도를 분석할 떄는 일반적으로 알고리즘이 실행하는 기본적인 연산 수행 횟수를 계산하고, 이를 입력 크기와 비교한다.

③ 시간 복잡도는 일반적인 최선, 평균, 최악의 경우로 나뉜다.

④ 시간 복잡도는 일반적으로 빅오(Big - O) 표기법을 사용하여 표기한다. 빅오 표기법은 입력 크기에 대한 함수의 상한(upper bound)을 나타내며, 알고리즘의 실행 시간이 이 함수보다 더 느리게 증가하지 않는 것을 보장한다.

  ㉠ 이를 수학식으로 나타내면 다음과 같이 나타낼 수 있다.

 

    ⓐ 이 부등식은 알고리즘 f의 실행 시간이 상한을 갖는다는 것을 말하며, g(n)의 상수배 이하의 실행 시간을 가진다는 것을 보장한다.

  ㉡ 위 수학 식을 빅오를 이용해 간단히 표기할 수 있다.

 

⑤ 다음 예시를 보자.

  ㉠ f(n) = 3n + 2를 빅 오 표기법으로 표기하면 O(n)이다.

 

    ⓐ f(n)은 4n 보다 느리게 증가한다.

 

    ⓑ 4는 상수이기 때문에 f(n) = O(n)이라고 표기할 수 있다.

 

  ㉡ f(n) = 10n^2 + 4*n + 2를 빅 오 표기법으로 표기하면 O(n^2)이다.

 

    ⓐ f(n)은 11n^2 보다 느리게 증가한다.

 

    ⓑ 11은 상수이기 때문에 f(n) = O(n^2)이라고 표기할 수 있다.

 

  ㉢ f(n) = 2^n + n^2를 빅 오 표기법으로 표기하면 O(2^n)이다.

    ⓐ f(n)은 2*2^n 보다 느리게 증가한다.

    ⓑ 2는 상수이기 때문에 f(n) = O(2^n)이라고 표기할 수 있다.

⑥⑦⑧⑨⑩⑪⑫⑬⑭⑮
㉠㉡㉢㉣㉤㉥㉦㉧㉨㉩㉪㉫㉬㉭
ⓐⓑⓒⓓⓔⓕⓖⓗⓘⓙⓚⓛⓜ