[알고리즘] 시간 복잡도

2022. 4. 11. 14:27·알고리즘/풀이 힌트
반응형

Big-O notation

프로그램의 성능을 알기 위해선 입력 크기, 하드웨어 성능, 운영체제 성능 .... 등 고려해야할 것이 많다. 

따라서 프로그램의 성능을 정확하게 파악하는 것은 불가능하다. 

 

그래서 대략적인 성능을 비교하기 위한 상대적인 표기법(Big-O notation)을 사용한다. 


O(1)에서 O(log n) .... O(n!)로 갈수록 점점 시간이 오래 걸린다. 

 

O(log n)과 O(n)이 눈으로 봤을 때는 크게 차이가 없는 것 같지만 n이 1024일 경우 O(n)은 1024번 반복하지만

O(log n)은 10번만 반복하게된다. 

 

O(3n - 30)이나 O(3 log n)같은 시간 복잡도는 본적이 없을 것이다. 

그 이유는 Big-O notation이 점근적 표기법을 따르기 때문이다.

 

점근적 표기법은 함수의 증감 추세를 비교하는 방법이다. 

프로그램을 쉽게 유지할 수 있도록 불필요한 부분을 버리고 가장 중요한 부분만 추려내서 함수를 간소화하는 것이다. 

6n^2 + 100n + 300 이라고 가정했을때 n의 값이 어느정도 계속 커진다고 했을 때, 6n^2은 100n + 300 보다 

커집니다. 

중요하지 않은 항과 상수 계수를 제거하면 이해를 방해하는 불필요한 부분이 없어져서 알고리즘 실행 시간에서 

중요한 부분인 성장률에 집중할 수 있다. 

 

Big-O natation 의 4가지 법칙

계수 법칙

상수 k가 0보다 클 때 f(n) = O(g(n)) 이면 kf(n) = O(g(n)) 이다. 

즉, n이 무한에 가까울 수록 k의 크기는 의미가 없다. 

합의 법칙

f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) + g(n) = O(h(n)) + O(p(n)) 이다. 

즉, Big-O 끼리는 더해질 수 있다. 

곱의 법칙

f(n) = O(h(n))이고 g(n) = O(p(n))이면 f(n) * g(n) = O(h(n)) * O(p(n)) 이다. 

즉, Big-O 끼리는 곱해질 수 있다. 

다항 법칙 

f(n)이 k차 다항식이면 f(n)은 O(n^k)이다. 

 

반응형
저작자표시 비영리 변경금지

'알고리즘 > 풀이 힌트' 카테고리의 다른 글

[알고리즘] 배열( 순차 리스트)  (4) 2022.04.20
[알고리즘] 자바스크립트 9가지 코드 트릭  (5) 2022.04.19
[알고리즘] 자료구조? 알고리즘?  (0) 2022.04.10
[알고리즘] 휴리스틱 알고리즘  (1) 2022.03.20
[알고리즘] 크루스칼 알고리즘(Kruskal Algorithm)  (7) 2022.02.16
'알고리즘/풀이 힌트' 카테고리의 다른 글
  • [알고리즘] 배열( 순차 리스트)
  • [알고리즘] 자바스크립트 9가지 코드 트릭
  • [알고리즘] 자료구조? 알고리즘?
  • [알고리즘] 휴리스틱 알고리즘
잉여개발자
잉여개발자
풀스택 개발자를 목표로 잉여롭게 개발 공부도 하면서 다양한 취미 생활도 즐기고 있는 잉여 개발자입니다.
  • 잉여개발자
    잉여로운 개발일지
    잉여개발자
    • 분류 전체보기 (789)
      • 개발정보 (36)
      • 개발환경 (7)
      • 개발생활 (19)
      • React (141)
        • 이론 (23)
        • 기능 (12)
        • 실험실 (88)
        • 버그 (6)
        • 패스트캠퍼스 (9)
        • Npm (3)
      • React Native (28)
        • 공통 (6)
        • TypeScript (3)
        • JavaScript (18)
        • 버그 (1)
      • Next.js (30)
        • 이론 (13)
        • 실험실 (13)
        • 버그 (3)
      • Web (35)
      • 알고리즘 (202)
        • 풀이 힌트 (39)
      • JavaScript (47)
      • TypeScript (29)
        • 기초 (27)
        • 실험실 (2)
      • Node.js (13)
        • 이론 (0)
        • 기능 (3)
        • 실험실 (9)
        • 버그 (1)
      • 도커 (4)
      • CCNA (22)
        • 이론 (4)
        • 문제 (18)
      • 취미생활 (167)
        • 잉여로운 칵테일 (2)
        • 잉여의 식물키우기 (130)
        • 잉여로운 여행기 (11)
        • 잉여의 제2외국어 (21)
        • 잉여로운 책장 (2)
      • Java (1)
        • Java의 정석 (1)
      • 꿀팁 공유 (3)
  • 태그

    redux
    next.js
    리얼학습일기
    ChatGPT
    react
    typescript
    Node.js
    다이소
    리액트
    ReactNative
    영어독학
    javascript
    프로그래머스
    네이버 부스트캠프
    자바스크립트
    알고리즘
    타일러영어
    Docker
    리얼클래스
    타입스크립트
    식물
    영어회화
    Babel
    바질
    덤프
    CCNA
    webpack
    바질 키우기
    네트워크
    CSS
  • hELLO· Designed By정상우.v4.10.1
잉여개발자
[알고리즘] 시간 복잡도
상단으로

티스토리툴바