시간 복잡도( time complexity) 는 프로그램이 실행되고 어떠한 알고리즘을 통과할때 완료하는 시간을 뜻한다.

 시간 복잡도를 표기하는 방법은 크게 3가지로 나누게 되며 기호는 오메가, 쎄타, 오가 있다. 대소문자에 따라서 리틀 오메가, 리틀 오표기법도 있지만 각각 함수의 기울기의 하한선과 상한선을 여유있게 표기하고 상한선과 하한선이 될수 없다는 의미를 포함 하고 있을 뿐이기 때문에 많이 쓰이지 않는다

Ω

 빅 오메가

 알고리즘 최고의 성능을 표기.

θ

 빅 쎄타

 알고리즘 대략의 성능을 표기.

O

 빅 오(Big-oh)

 알고리즘 최악의 성능을 표기


이중에 가장 많이 쓰이는 표기법은 빅 오 표기법으로 최악의 상황에서 이 정도 까지는 성능을 보장한다는 의미를 갖고 있다.

 시간 복잡도를 표기할때 계수나 상수는 무시하게되는데 O(1)이나 O(10000)은 같다고 보게 되는데 1이나 10000이나 입력되는 값에 따라 알고리즘의 속도가 변화 없기 때문에 무시된다.

O(n), O(100n), O(n-1)의 경우도 같다고 보게 되는데 n의 값이 무한데로 커졌을때 -1이나 계수는 무시할수 있다고 보기 때문이다.

간단하게 빅오 표기법을 사용하는 방법은

첫번째로 입력값(n)이 무엇인지를 확인한다.

두번째로 수행 연산 횟수를 n의 식으로 표현한다.

세번째로 가장 차수가 높은 항만 남기고 그 아래 차수와 상수는 지운다.

주의할점으로 반복문이 두개가 나란히 있는 경우 더 높은 차수의 for문을 알고리즘 성능으로 사용하고 상수가 곱해져 있고 옆에 n이 더 있더라도 최고 차수만 사용한다.

'Algorithm' 카테고리의 다른 글

Dynamic Programming(동적 계획법)  (0) 2014.07.17
nodejs에서 mysql를 사용하던중 Mybaist같은 Data base 개발 프레임 워크가 없나 찾아 보았습니다. mybatisnodejs와 nobatis가 있지만 사용법을 잘모르겠어서 조잡하게나마 mybatis처럼 만들어 보았습니다. sax parser를 사용한 xml 파서인 xml-digester를 사용해서 만들었고 사용법은 아래 내용을 참고하시면 되고 mysql module이 필요하다는 것을 미리 말씀드립니다. npm install yhbatis로 module을 받은후에 서버 시작 부분에서 모듈을 global로 설정 및 생성하시면 다른 곳에서 사용하기 편리합니다.



매트랩 삭제때에 위와 같은 창이 나오면서 삭제가 되지 않는것은 윈도우즈 테마 때문이기 때문에


1. 바탕화면 오른쪽클릭->개인설정->컴퓨터의 시각 효과 및 소리 변경에서 아래로 드래그->windows 고전(classic)의 테마 클릭

2. 이제 매트랩을 삭제하면 됩니다. 시작->Matlab->Uninstall

'Error' 카테고리의 다른 글

sendUserActionEvent() mView == null 에러  (0) 2015.03.16

 03-16 15:48:18.638: E/ViewRootImpl(15395): sendUserActionEvent() mView == null

삼성 계열 디버깅 모드 때 발생됨. 무시해도 됩니다.

'Error' 카테고리의 다른 글

matlab bummer uninstallation error Exception calling main  (0) 2015.03.17
개발용과 배포용의 인증서에 따라서 gateway에서 sendbox의 유무를 다르게 주어야함.

설치된 xampp의 폴더에서 아래경로의 파일을 열어줍니다.


C:\xampp\apache\conf\extra\httpd-vhosts.conf


처음 열게 되면 모든 부분이 주석처리가 되있습니다. 아래 처럼 설정들을 입력해줍니다.


NameVirtualHost *

<VirtualHost *>

DocumentRoot "C:\xampp\htdocs"

ServerName simuruk.com

</VirtualHost>

<VirtualHost *>

    DocumentRoot "C:/xampp/htdocs2"

    ServerName m.simuruk.com

<Directory "C:/xampp/htdocs2">

Require all granted

</Directory>

</VirtualHost>


DocumentRoot 는 루트폴더를 지정하는 부분이고

ServerName은 루트 폴더가 연결되는 주소입니다.


Require all granted는 모든 접근에 제한을 두지 않는다는 내용으로 넣어주지 않으면

m.simuruk.com에서는 403 EORROR를 보실수 있을겁니다.

시작 전에 서버를 시작할 위치에 명령프롬프트 창을 켜서 npm install request를 설치해줍니다.
동적 계획법의 원리는 매우 간단하며 작은 문제가 중첩되어있는 문제를 해결하는데 사용하는 방법이다. 일반적으로 문제를 풀때 하위의 작은 문제들을 해결한다음 합쳐서 결과를 얻게 되는데 작은 문제를 해결할때 생기는 반복적인 작업의 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결 할수 있다. 예를 들어 피보나치 수열을 구하는 함수는 다음과 같다. 이때, fibonazzi(5)를 구한다 fibonazzi(5) = fibonazzi(4) + fibonazzi(3) = fibonazzi(3) + fibonazzi(2) + fibonazzi(2) +fibonazzi(1) = fibonazzi(2) + fibonazzi(1)+fibonazzi(1)+fibonazzi(0)+fibonazzi(1)+fibonazzi(0))+fibonazzi(1) = fibonazzi(1)+fibonazzi(0)+fibonazzi(1)+fibonazzi(1)+fibonazzi(0)+fibonazzi(1)+fibonazzi(0))+fibonazzi(1) 이때에 fibonazzi(2)의 하위 계산은 반복된다. 이 값을 저장하는 객체를 두고 하위 작업의 결과 값을 저장해 둔다면 복잡도는 O(n)이 된다. 다음 코드는 동적계획법을 사용한 피보나치의 예이다. 코드를 간단히 보게되면 하위 문제의 해결값을 넣어둘 배열 m을 두게 됩니다. 피보나치 0과 1의 값은 1이기 때문에 m[0]과 m[1]에 1을 넣어주고 m[2]부터 사용자가 구하고자 하는 값인 m[n]까지 구하게 됩니다. 이때 바로 하위의 값은 이미 구해서 메모리에 있기 때문에 복잡도는 높아지지 않고 구할수 있게 됩니다. 결과적으로 m[n]의 값은 하위 점화식으로 부터 분할정복법으로 구한 값과 같은 값을 구한게 됩니다.

'Algorithm' 카테고리의 다른 글

Big O Notation( 빅오 표기법 ), 시간복잡도.  (0) 2015.06.22

+ Recent posts