[자료구조] 002. 시간 복잡도, Big-O

* 본 포스팅은 유튜브에 있는 신찬수 교수님의 자료구조 강의 중 '시간복잡도' 내용을 복습하기 위해 기록한 것

 

1. 자료구조와 알고리즘

• 자료구조란 자료(data)를 저장할 수 있는 공간(memory) + 읽기,쓰기,삽입,삭제,탐색과 같은 연산으로 구성된 것
• 알고리즘은 입력된 data를 유한한 횟수의 연산을 반복하여 정답을 출력하는 것
• => 따라서 자료구조와 알고리즘은 뗄 수 없는 관계

 

2. 인류 최초의 알고리즘 : GCD 계산

• gcd_sub, gcd_mod, gcd_rec 각각의 방법에 따라서 구현 가능

 

3. 알고리즘의 성능

• 자료구조와 알고리즘의 성능은 대부분 수행 시간으로 정의되는 것이 일반적
• 하드웨어와 소프트웨어 환경에 구애받지 않는 객관적 컴퓨터 모델을 가정하기 위해서
• 가상 컴퓨터 / 가상 언어 / 가상 코드 사용
  • 가상컴퓨터 : 폰노이만 구조를 따른 RAM모델
  • 기본연산 : 대입 / 산술 / 비교 / 논리 / 비트 연산 등 단위 시간 내에 할 수 있는 연산
  • 가상 언어 : 자연어보단 간단 명료 BUT 프로그래밍 언어보단 융통성 있는 언어이며, 명령어 집합 및 기본 연산 제공

 

4. 알고리즘의 시간복잡도

• 모든 입력에 대해 수행시간을 측정할 수 없기 대문에 '최악의 경우의 입력'을 가정한 후 수행시간 측정
• 정확한 수행시간은 아니지만 어떤 입력에 대해서도 수행시간이 작다는 것을 보장해줌

 

5. Big-O

• 증가율의 관점에서, N이 커지면 같은 수행시간을 가진다고 보면 됨
• 따라서 최고차항을 통해 수행시간을 나타내는 함수의 대략적인 형태를 도출
• 아래 사이트를 통해 시간 복잡도를 시각적으로 확인 가능

https://www.bigocheatsheet.com/