[RW Data Structures & Algorithms in Swift] Chapter 2: Complexity

Scalability란?

아키텍쳐의 관점에서 - 앱에 변경이 얼마나 쉬운지
데이터베이스 관점에서 - 데이터베이스로부터 데이터를 불러오거나 저장하는데 걸리는 시간
알고리즘의 관점에서 - 입력값이 증가함에 따라 소요되는 실행시간과 메모리의 정도

시간복잡도란?

비용이 많이 드는 알고리즘도 작은 데이터셋을 처리할 때는 빠르게 느껴질 수 있다.
왜냐하면 하드웨어가 많이 발전했기 때문이다. 그러나 데이터의 양이 늘어나면 해당 알고리즘의 비용이 상당하다는 것을 금방 알 수 있다.

그렇기 때문에 작은 데이터셋보다는, 많은 양의 데이터셋을 처리할 때 알고리즘의 실행시간이 어떻게 달라지는지 중요하다.

시간복잡도란 ?

• 입력값에 들어오는 양이 증가함에 따라 변화하는 알고리즘의 실행시간의 패턴을 말한다.

공간복잡도란 ?

• 알고리즘에 입력값에 들어오는 양이 증가함에 따라 변화하는 리소스(메모리) 사용량의 패턴을 말한다.

Constant Time, Linear Time, Quadratic Time, Logarithmic Time

Constant Time - 상수 시간
Linear Time - 선형 시간
Quadratic Time - 이차 시간
Logarithmic Time - 로그 시간 - O(log n)
Quasilinear Time - 준선형 시간 - O(n log n)

Logarithmic Time

로그 시간이 나오는 알고리즘을 작성하기 위해서는 하나의 전제조건이 필요하다.

정렬된 요소들의 모음이어야한다.

로그의 밑 (base)가 무엇인지는 중요하지 않다. 왜냐하면 Big O 노테이션이 관심 있는 것은 알고리즘의 실행시간이 어떤 패턴에 따라 변화하는지 이기 때문에 로그의 밑이 10이거나 2인지 자연 로그인지 중요하지 않다.

Quasilinear Time

준선형 시간.

스위프트의 sort 가 이 시간복잡도에 해당.
가장 자주 볼수있는 시간복잡도.
선형 시간보다 느리지만 이차 시간보다는 굉장히 빠르다.

그 외의 시간복잡도

이 외에도 Polynomial Time - 다항 시간복잡도
exponential time complexity - 지수 시간복잡도
factorial time complexity - 팩토리얼 시간복잡도

등이 있다.

시간복잡도 비교

func sumFromOne(upto n: Int) -> Int {
  var result = 0
  for i in 1...n {
    result += i
  }
  return result
}
  
sumFromOne(upto: 10000)

위는 O(n)

func sumFromOne(upto n: Int) -> Int {
  (1...n).reduce(0, +)
}
sumFromOne(upto: 10000)

위의 reduce 또한 O(n)이지만 컴파일되어있는 코드이기 때문에 약간 더 빠르다.

func sumFromOne(upto n: Int) -> Int {
  (n + 1) * n / 2
}
sumFromOne(upto: 10000)

가우스가 초등학생때 1부터 100까지 더하는 방법을 찾아낸 방법임
gaussian sum이라고함.
1부터 n까지 더한 값을 빠르게 찾아낼 수 있는 방법
시간복잡도는 O(n)