본문 바로가기
컴퓨터

[알고리즘] 알고리즘 성능

by Luyin 2012. 7. 29.

좋은 알고리즘 이란??


  1. 메모리를 적게 먹고
  2. 속도가 빠르고
  3. 간결한
알고리즘을 말한다.


알고리즘 성능을 표현하는 방법

점근 표기법 : 알고리즘의 수행 시간을 대략적으로 나타내는 방법을 말한다.
 최고차 항을 제외한 나머지 모든 항과 모든 계수를 제거한다.
  1. O(Big O) 표기법            : 최악의 경우
  2. Ω(BIg Omega) 표기법    : 최선의 경우
  3. Θ(Big Theta) 표기법    : 최악의 경우와 최선의 경우를 모두 만족하는 경우??????

일반적으로 O(Big O) 표기법을 가장 많이 쓴다.

ex) 데이터의 크기 n에 대한 최대의 수행 시간이 2n^2+4n인 알고리즘의 경우
O(n^2) 이다.

가장 빠른 접근 속도를 갖고 있는 자료구조

  •  이진 탐색 트리
  •  해시 테이블


가장 빠른 정렬 속도를 갖고 있는 자료구조

  • 대규모 데이터 : 퀵 정렬
  • 소규모 데이터 : 삽입 정렬


가 함수 

설명 

알고리즘 

O(1) 

해당 알고리즘이 최악인 경우에도 일정한 상수 시간에 종료된다는 것을 의미합니다. 

해시 테이블 
     
     
     
     
     
     





댓글0