확장성

알고리즘에서 확장성은 입력 크기가 증가함에 따라 실행 시간 및 메모리 사용량 측면에서의 알고리즘의 선능을 말합니다.

소량의 데이터로 작업 할 때 expensive한 알고리즘도 빠르다고 느낄 수 있습니다. 그러나 데이터 양이 증가하면 expensive한 알고리즘은 나빠 질 수 있습니다. 이때 얼마나 나빠질수 있을까요? 이를 정량화 하는 방법을 이해하는 것은 중요한 기술입니다.

여기서는 실행 시간과 메모리 사용이라는 두 가지 확장성 수준에 대한 BigO 표기법을 살펴 봅니다.

Big O는 최악의 상황에 대해서 시간을 확인

진행순서

• Time complexity - 시간복잡도
  • Constant Time - 일정한 시간
  • Linear Time - 선형 시간
  • Quadratic Time - 이차 시간
  • Logarithmic Time - 대수 시간
  • Quasilinear Time - 준 선형 시간
  • Other Time complexities - 다른 시간 복잡도
    • 다항식 시간, 지수 시간, 팩토리얼 시간 등
  • Comparing time complexity - 시간 복잡도 비교
• Space Complexity - 공잔 복잡성
• Other notaions - 다른 표기 법
  • Big Omega, Big Theta

Time complexity - 시간 복잡도

소량의 데이터의 경우 최신 하드웨어의 속도로 인해 가장 expensive한 알고리즘도 빠르게 보일 수 있습니다. 그러나 데이터가 증가함에 따라 expensive한 알고리즘의 비용은 점점 뚜렷해 집니다.

시간 복잡도는 입력 크기가 증가함에 따라 알고리즘을 실행하는 데 필요한 시간을 측정한 것입니다.

Constant Time - 일정한 시간

Constant time algorithm은 입력 크기에 관계없이 동일한 실행 시간을 갖는 알고리즘입니다.

배열의 첫번째 요소만 검사하는 함수가 있습니다. 이 함수의 시간 복잡도는 입력(배열의 크기)에 관계없이 항상 같은 시간이 걸립니다.

Linear Time - 선형 시간

func printNames(names: [String] {
	for name in names {
		print(name)
	}
}

이 함수는 모든 이름을 문자열 배열로 인쇄합니다. 입력 배열의 크기가 증가함에 따라 for 문의 반복 횟수는 같은 양만큼 증가합니다.