시간 복잡도란 무엇인가

[SeoYeonBae]

• 알고리즘을 수행하는 데 몇 번 연산이 이루어지는 지 표기한 것
• 조건문, 반복문, 재귀 호출을 중요하게 생각하여 시간 복잡도를 계산함

• 빅오표기법

  • 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용함
  • 여기서 시간 복잡도는 시간 효율성을 의미하고 공간 복잡도는 메모리 효율성을 의미함
  • O(1) : 스택에서 push, pop
  • O(logN) : 이진트리
  • O(N) : for문
  • O(NlogN) : 퀵정렬, 병합정렬, 힙정렬
  • O(N^2): 이중 for 문, 삽입정렬, 거품정렬, 선택정렬
  • O(2^N) : 피보나치

[KangYoonjoo]

시간복잡도

• 알고리즘 수행에 몇 번의 연산이 이뤄지는 지를 표기한 것
• Big-O 표기법
  • O(1) : 프로그램에서 1라인이 실행되는 경우.
  • O(n) : 입력 데이터 크기에 비례해 처리 시간 증가. (for문, 반복문)
  • O(NlogN) :입력 데이터가 많아질수록 처리 시간이 로그만큼 감소. (이진탐색)
  • O(n^2) : 데이터가 많아질수록 처리 시간이 로그만큼 증가. (병합정렬, 퀵정렬)
  • O(2^n) : 데이터가 많아질수록 처리 시간이 기하급수적으로 증가 (피보나치 수열, 재귀)

[Han7sunny]

시간복잡도

• 알고리즘의 수행시간 분석 결과
• 절대적인 실행 시간이 아닌 알고리즘을 수행하는데 연산이 몇 번 이루어지는지를 표기한다.

점근 표기법

n이 커질 때 알고리즘의 단계가 얼마만큼 증가하는지

• O(Big O) 표기법: 알고리즘 성능이 최악인 경우(수행 시간의 상한)를 나타낼 때 사용
  • 알고리즘을 사용하는 어떤 경우에도 보장되는 알고리즘의 성능
• Ω(Big Omega) 표기법: 알고리즘의 성능이 최선인 경우(수행 시간의 하한)를 나타낼 때 사용
• Θ(Big Theta) 표기법: 알고리즘이 처리해야 하는 수행 시간의 상한과 하한을 동시에 나타냄

[jangyejoo]

• 시간 복잡도란 알고리즘을 수행할 때 몇 변의 연산이 이뤄지는지 표기한 것
• 조건문, 반복문, 재귀 호출에 영향을 크게 받기 때문에 그 위주로 계산함
• 빅오 표기법 : 최악의 상황일 때 시간복잡도, 공간복잡도 표기법