[Study] 시간복잡도, Big-O

🚩시간복잡도란?

• 알고리즘의 성능을 표기하기 위해 사용한다.
• '완료까지 걸리는 절차의 수'라고 생각하면 된다
• 완료까지 N단계가 걸리는 알고리즘의 시간복잡도는 O(N)이다.
• 가장 시간복잡도가 낮은 알고리즘을 선택하여 사용한다

🚩 점근적 분석

• 시간 복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다
• 임의의 함수가 N -> 무한대 일 때 어떤 함수 형태에 근접해지는지 분석

-상수는 무시된다
n + 20 => n

-계수는 무시된다

2n => n

-가장 큰 차수를 제외한 차수는 제외된다

2n^2 + 3n => n^2

🚩 점근적 표기법

• 점근적 분석을 통해 실행시간을 단순하게 표현
• 이 때 점근적 표기법으로 표현함
• Ω (lower bound) : 최소 실행 시간
• O (upper bound) : 최대 실행 시간
• θ : 평균 실행 시간

for(int i =0; i<n ; i++){
    if( i == s) break;
}

 

위 코드의 시간복잡도는 Ω(1), O(N), θ(N/2)= θ(N) 이다.

 

🚩 빅 O 표기법의 종류

O(1)

-상수 시간 복잡도
-문제를 해결하는데 오직 한 단계만 처리함

public void method(){
    System.out.println("Big-O");
}

O(N)

- 선형시간복잡도
- 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐

- 선형 검색(Linear Search)이 이에 해당됨

for(int i =0; i<n ; i++){
    System.out.println("Wanna Go Home");
}

O($N^2$)

- 2차 시간 복잡도라고 함
- 문제를 해결하기 위한 단계의 수가 입력값 n의 제곱

for(int i = 0; i<n ; i++){
    for(int j = 0; j<n; i++){
        System.out.println("hello");
    }
}

O(logN)

-로그 시간 복잡도

- 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬

- 이진 검색이 이에 해당됨

 

시간복잡도 효율

 

시간 복잡도 효율은 O(log N) > O(N) > O(N^2) 이다