• 목차

효율성 분석

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
• 메모리 양 → 공간 복잡도(space complexity)
  • 정적 공간 + 동적 공간
• 수행 시간 → 시간 복잡도(time complexity)

  • 시간 복잡도 구하기

    

시간 복잡도

• 문제를 해결하는데 걸리는 시간과 입력의 함수

• 컴퓨터 과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것

• 시간 복잡도를 표현 하는 방식으로 Big-O 표기법을 사용

• O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

• 오른쪽으로 갈수록 계산 시간은 오래 걸린다!

  

O(1)

• 상수 시간: 입력 값 n이 주어졌을 때, 연산이 1번만 수행

public class timeComplexity{
 
    public static void main(String[] args){
 
        int constant = 1; // 시간 복잡도: O(1)
 
    }
}

O(log n)

• 로그 시간: 입력 값 n이 주어졌을 때, 특정한 요건에 따라 필요한 단계가 연산이 줄어 든다.