패스트캠퍼스 챌린지 5일차

알고리즘 복잡도 표현 방법

 1. 알고리즘 복잡도 계산이 필요한 이유

    - 다양한 알고리즘 중 어느 알고리즘이 더 좋은지 분석하기 위해, 복잡도를 정의하고 계산

 

 2. 계산항목

   1. 시간 복잡도 : 알고리즘 실행 속도 *

   2. 공간 복잡도 : 알고리즘이 사용하는 메모리 사이즈

 

 프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문이다.

 

알고리즘 성능 표기법

  • Big O (빅-오) 표기법 : 0(N)

   - 알고리즘 최악의 실행 시간을 표기

   - 가장 많이 / 일반적으로 사용

   - 최악의 실행 시간을 표기하는 이유는 최악의 상황에도 이정도 성능은 보장한다는 의미

  • Ω (오메가) 표기법 : Ω(N)

   - 알고리즘 최상 실행시간 표기  

  • Θ (세타) 표기법 : Θ(N) 

   - 알고리즘 평균 실행시간 표기

  

3. Big-O 표기법

  • O (입력)

   - 입력 n에 따라 결정되는 시간 복잡도 함수

 

 시간 복잡도 크기 

  O(1) < O(logn) < O(N) < O(nlogn) < O(N^2) < O(2^n) < O(n!)

   - 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 된다.

 

 표기 시 앞에 상수는 제거하고 표현한다 EX) O(3n) => O(n) , O(2n^2) => O(n^2)

 

 

알고리즘 1 : 1부터 N까지의 합을 구하는 알고리즘

시간 복잡도 : O(n)
public int sum(int n){
  int total = 0;
  for(int i = 0; i < n; i++){ // 반복문이 N번 반복
    total += i;
  }
    return total;
}

 

알고리즘 2 : 1부터 n까지의 합을 구하는 알고리즘 2  n(n+1) / 2

// 반복문을 사용하지 않고 n이 늘어남
public int sum(int n){
  return n*(n+1) / 2;
}

 

 

5일차 인증

 

 

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

https://bit.ly/37BpXiC

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