[알고리즘] 패스트캠퍼스 챌린지 07일차

알고리즘 복잡도

하나의 문제를 푸는 알고리즘은 다양한데, 어느 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산해 이를 통해 판단함.

알고리즘 복잡도 계산 항목

• 시간 복잡도 : 실행 속도 >> 이게 가장 중요하다.
• 공간 복잡도 : 메모리 사이즈

=> 가장 많이 영향을 미치는 요소는 반복문이다..

알고리즘 성능 표기법

• Big O (빅-오) 표기법: O(N) >> 이걸 익히자.
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용함
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문
• Ω (오메가) 표기법: Ω(N)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기
• Θ (세타) 표기법: Θ(N)
  • 오메가 표기법은 알고리즘 평균 실행 시간을 표기

Big-O 표기법

• O(입력)
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(𝑙𝑜𝑔𝑛) < O(n) < O(n𝑙𝑜𝑔𝑛) < O(𝑛²) < O(2ⁿ) < O(n!)
  • 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 되고, 가장 큰 영향을 미치는 n 의 단위로 표기
    • 만약 시간 복잡도 함수가 2𝑛² + 3n 이라면
      • 가장 높은 차수는 2𝑛²
      • 상수는 실제 큰 영향이 없음
      • 결국 빅 오 표기법으로는 O(𝑛²)

테스트할 문제로 1부터 N 까지의 합을 구하는 문제가 주어졌다.
[#1] 합을 기록할 변수를 만들고, 1부터 n까지 1씩 증가하면서 반복문을 돌려준다.

func sum(n: Int) -> Int { var total: Int = 0 for number in 1...n { total += number } return total }

이 경우 시간 복잡도는: O(n)

[#2] 1부터 n까지의 합을 구하는 공식이 있음. (n*(n+1)) / 2 (^^;;)

func sum(n: Int) -> Int { return (n * (n + 1)) / 2 }

이 경우 시간 복잡도는: O(1)

따라서 [#1] 알고리즘보다 [#2] 알고리즘이 성능이 좋다!!

예전에 Big-O 표기법에 대해서 알고나서 일하면서 반복문 줄여나가고.. 시간 복잡도도 계산해 보면서 예쁘게 코드 짜고 싶었는데..
갑자기 들어오는 유지보수건, 신규 개발건 처리하느라 일정에 쫒기다가 어느새 잊고있었다ㅠㅠ
강의들으면서 문제 풀면서 익숙해지고 습관들여보려고 노력해야겠다!!

오늘의 강의 인증샷 ㅎㅎ 오늘은 코드 짤 건 많이 없고 거의 개념 위주였다.

어찌저찌 일주일은 채웠다!!
대박... 이제 3주 남았다.. ^^;;


https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.