SPATIUM Desktop
주소복사
About Operating System Languages Tools Favorites Notice Visit TEST  
     Notice (47)
     News (10)
   ID  
   Password  
  |  
  Location United States
  IP Address 3.225.221.130
2022. 12
123
4567
8
910
11121314151617
18192021222324
25262728293031
Title

Big-Oh Notation( 시간 복잡도 )

Writer 김태우 Date 2013-02-28 15:08:03 Visit 3628
log, 로그의 밑, 로그의 진수

 

Big-Oh Notation

 

- 데이터의 수 n 과 그에 따른 시간복잡도 함수 T(n)을 구하는 위하여 Big-Oh 표기법을 사용한다.

- 함수 T(n)에서 가장 영향력이 큰 부분이 어딘가를 따지는 것이다.

- 데이터 수의 증가에 따른 연산횟수의 증가 형태를 표현.

 

예)

    T(n) = n2 +3n + 1, 이식에서 가장 영향력이 큰 T(n) = n2 로 표현한다.

다음 표는 n2 이 차지하는 비율을 정리한 것이다.

n n2 2n T(n) n2의 비율
10 100 20 121 83.33%
100 10000 200 102001 96.04%
1000 1000000 2000 1002001 99.98%
10000 100000000 20000 100020001 99.99%

 

결국,  T(n) = n2 +3n + 1 의 빅오는 n이며, n 의 증가 및 감소에 따른 T(n)의 변화 정도가 n2의 영향을 가장 많이 받는 것을 나타냄. 

O(n2) 표기, Big-Oh of n(빅오 오브 n2 )

 

대표적인 Big-Oh

O(1)

    : 상수형 빅-오, 데이터 수에 상관없이 연산횟수가 고정인 유형의 알고리즘

O( log n )

    : 로그형 빅-오, 데이터 수의 증가에 비해서 연산횟수의 증가율이 훨씬 낮은 알고리즘, 이상적인 유형

O(n)

    : 선형 빅-오, ㄷ이터의 수와 연산횟수가 비례하는 알고리즘

O( n log n)

    : 선형로그형 빅-오, 데이터의 수가 두배로 늘어날때, 연산횟수는 두배 조금 넘게 증가하는 알고리즘

O( n2 )

    : 데이터의 수의 제곰에 해당하는 연산횟수를 요구하는 알고리즘, 중첩 반복문 연산으로 바람직하지 못한 형태

O( n3 )

    : 데이터 수의 세제곱에 해당하는 연산횟수를 요구하는 알고리즘, 삼중 중첩 반복문 연산으로 무리가 있는 알고리즘

O(2n)

    : 지수형 빅-오, 사용하기에 매무 무리가 있는 알고리즘

 

* log 간단 설명

ax=b 일때, x=logab 를 만족, 여기서 a를 로그의 '밑', b를 로그이 '진수'라 함.

예)

    24=16 일때, 4=log216 입니다.

    로그의 밑 10일겨우 생략 가능 합니다.  log10x 는 log x 라고 표현.

 

 

Title Date Visit
POSTMAN, 토큰조회API의 결과값 token을 요청 Header 값으로 사용 2019-07-17 3768
BMT, POC, prototyping, pilot 2019-06-10 1459
클래식 100곡 순위 2019-03-11 2637
AWS 참고 자료 2019-03-06 1852
MAC 단축키 2019-02-19 1451
Big-Oh Notation( 시간 복잡도 ) 2013-02-28 3628
Sort algorithm 2013-02-28 2340
UTF-8 BOM( Byte Order Mark ) 2013-02-28 2587
METADATA ( 메타데이터 ) 2013-02-27 2145
Responsive Web ( 반응형 웹 ) 2012-07-31 2392
사이트 트래픽 관련 2012-05-16 3459
Copyright (C) SPATIUM. All rights reserved.
[SPATIUM]WebMaster Mail