목록열기  Hot News (4) |
오늘의 분석 보내드립니다. HTC 가 자체적인 OS 준비하고 있다는 루머와 모토롤라가 자체의 운영체제를 사들였다는 루머는 지속적으로 확인해봐야겠습니다.^^
|
| |||||||||||||||||||
category
2010년 10월 25일 월요일
모바일 브라우저
String array to arraylist
String array to arraylist | ||
|---|---|---|
| Greenhorn Joined: Jan 21, 2006 Posts: 1 | posted 2006년 3월 21일 화요일 오후 1:28   0  | |
 | ||
| Ranch Hand Joined: Jan 17, 2006 Posts: 1285 | posted 2006년 3월 21일 화요일 오후 2:24 0 | |
2010년 10월 23일 토요일
0~n-1 난수만들기
1. 난수(random number) 발생기(generator) 구현의 어려움 표준 C 라이브러리에는 rand()라는 함수가 있다. 물론 각각의 시스템에 따라 이 함수의 구현(implementation)은 완전하지 않을 수 있다. 그러나, 이 함수보다 더 좋은 성능을 가진 함수를 직접 만들기란 쉬운 일이 아니다!
직접 난수 발생기를 만들려고 한다면, 읽어야 할 책이 많다! r250, RANLIB, FSULTRA 등의 라이브러리가 있긴 하지만..
2. 특정 범위 내에서 난수를 발생시키고 싶은데 다음과 같이 하는 것은 (0에서 N-1까지의 수치를 리턴) 매우 서투른 방법이다
rand() % N /* POOR */
왜냐하면, 대부분의 난수 발생기에서 하위(low-order) 비트들은 그리 랜덤하지 않기 때문이다. 따라서, 다름과 같이 하는 것이 좋다.
(int)((double)rand() / ((double)RAND_MAX + 1) * N)
실수를 쓰기 싫다면, 다음과 같이 해도 좋다.
rand() / (RAND_MAX / N + 1)
두 방법 모두 RAND_MAX를 (
(어쨌든, RAND_MAX는 rand()가 리턴할 수 있는 최대 수치를 나타낸다는 것을 기억해야 한다. RAND_MAX에 다른 수치를 대입할 수는 없으며, rand()가 다른 범위의 수치를 리턴하도록 해 주는 다른 방법은 존재하지 않는다!)
만약 0과 1사이의 범위를 가지는 난수 발생기를 가지고 있다면, 그리고 0과 N-1사이의 범위를 가지는 정수 난수를 만들고 싶다면, 단순히 그 난수 발생기의 수치에 N을 곱하면 된다!
3. 프로그램을 실행시킬 때마다, rand()는 일정한 순서로 난수를 발생시킨다. 왜 그런가 srand()함수를 불러서 가상 난수 발생기에게 (pseudo-random number generator) 초기 값을 임의로 주면 된다. 이 초기값은 'seed'라고 하며, 대개는 현재 시간이나, 유저가 어떤 키를 누르기 전까지의 시간차로 지정한다. (물론 어떤 키를 누르기 전의 시간을 얻는 방법은 이식성있게 만들기가 힘들다!) (일반적으로 프로그램 내에서는 srand() 함수를 한번만 불러주어도 충분하다! rand()를 부를 때마다, srand()를 부른다면, 충분한 임의의 수치를 얻을 수 없다.)
4. 참/거짓을 나타내는 난수가 필요하다. 그래서 rand() % 2를 썼는데, 계속 0, 1, 0, 1, 0 만을 반복하더라 엉성하게 만들어진 가상 난수 발생기는 (pseudo random number generator) 하위(low-order) 비트들에 대해서는 그렇게 랜덤하지 않다. 상위(high-order) 비트를 쓰는게 좋다.
5. 그럼 도데체 일반적이거나 정규 분포를 위한 난수는 어떻게 발생시킬 수 있는가 Marsaglia씨에 의해 개발되고 Knuth씨가 추천한 방법이다.
#include double gaussrand() if (phase == 0) { V1 = 2 * U1 - 1; X = V1 * sqrt(-2 * log(S) / S); phase = 1 - phase; return X; [출처] 난수 발생의 난해함|작성자 재즈 |
2010년 10월 22일 금요일
Big O notation
자료구조에서 빅오 (Big O)란 무엇인가요
- zoojjang
- 2005.04.01 10:50
- 답변
- 3
- 조회
- 8,023
자료구조에서 빅오 (Big O) 표기법이 무엇인가요
좀 자세히 설명좀 부탁드려요.
- 신고
질문자 채택된 경우, 추가 답변 등록이 불가합니다.
질문자 인사
<<>>
for (int i = 0; i < n; i++)
{
명령...
}
이런 문장은 n번 수행을 하기 때문에 O(n)입니다. i < 2n도 마찬가지로 1차이므로 O(n)입니다.
------------------------------------
for (int i = 0; i < n; i++)
{
for (int k = 0; k < n; k++)
{
명령...
}
}
이 문장은 O(n^2)입니다. 즉 n의 제곱에 비례해서 명령이 반복되게 되는 거죠.
버블소트를 구현하면 두번째와 같은 명령어 구조를 띠기 때문에 버블소트의 계산복잡도는 O(n^2)이 되는 겁니다.
머 리쓰는 게임 중에 특수한 마방진(5 X 5)이 있다고 합시다. 어떤 사람은 25개의 수열이 모두 들어가는 경우(25!)를 감안하여 풀도록 프로그램하였다면 이것은 O(n!)이 되는 겁니다. 그에 반해 어떤 사람은 특수한 요령을 알아내서 5개씩 묶어서 5번 안에 해결되게 프로그램을 구현한다면 O(n^2)이 되는 겁니다.
즉 길이가 n인 프로그램에서 명령을 수행할 때 n에 얼마나 비례하여 명령이 수행되는가가 계산복잡도입니다.
- 지식/in icarte 님의 답변내용
질문자 인사
<<>>
출력하는 프로그램입니다. 그렇다면 이 프로그램의 라이프사이클중 가장
많은 부분을 차지하는 것이 n번의 for문 일 것입니다.
즉, 프로그램의 실행속도에 가장 지대한 영향을 끼치는 부분은 n회 for문!
어떻게 해도 프로그램의 실행속도는 최대 n번을 넘지 못합니다.
n번을 넘기는 컴퓨터가 있다면 미친 컴퓨터이거나 고장난 컴퓨터겠지요~! ^^;
이렇듯 빅오는 다음과 같이 해석하시면 쉽습니다.
O(n) : 최악의 경우 n번까지 돌면 프로그램은 끝낼 수 있다!
즉 힘껏 돌려봐야 최대 n번이면 끝낼 수 있다는 뜻이지요.
O(1), O(log n), O(n^2), .... 등등 다 마찬가지입니다. 그 이상은 안 넘긴다는
말입니다.
예를 들어.... 어떤 코드를 가중치에따라 측정해보니 "2n^3 + 4n + 7" 이렇게
나왔고, 이 것의 최대 한계 값인 O()를 알아보라고 했습니다.
보아하니 n^3이 있네요! 삼중루프가 있었나 봅니다. 그렇다면 4n이고 7이고
다 필요없지요~! 프로그램의 실행속도에 가장 많은 영향을 끼치는 것은 n^3
입니다. 따라서 위 식의 Big O는 O(n^3)이라고 말할 수 있는 것입니다.
n이 각각 10 정도면 그저그렇겠지만... 만약 1000번 정도만 된다고 생각하면
삼중루프일때... 약 1000000000! 헉! 1억번을 실행해야 하죠! 물론 중간에
끝날 수도 있지만, 최악의 경우에는 1억번을 돌고돌아야 합니다...
시간이 많이 걸리겠지요... 실제 상용프로그램이 이렇게 돌아간다면 사람들
분명 짜증날겁니다. 또 이 프로그램 안쓰겠지요... ^^; 누가 쓰겠습니까? ㅎㅎ
그래서 알고리즘의 개선은 중요합니다. 빅오는 이런 알고리즘을 개선하기 위한
척도를 제공해 주는 것입니다. 빅오 이외에 몇가지 더 있죠? 그 것들도 마찬가지
입니다.
두서없이 적었습니다... 어떻게 이해가 되시는지요? ^^
| notation은 단어 의미대로 '표기법' 이라고 생각하시면 됩니다. 그러니까
Big-O notation 은 '대문자 O 표기법' Omega 는 'Ω 표기법', (Big-omega 라고 하기도 합니다) Theta는 'Θ 표기법' (역시 Big-Theta라고 합니다)
이라고 생각하시면 됩니다.
수업을 들으셨다니 O(n), O(log n) 같은 것들을 이미 보셨으리라 생각합니다. O 대신에 Ω나 Θ가 있을 수도 있죠. 이것들이 바로 그 notation들입니다.
세 가지 다 님께서 말씀하신 '알고리즘 효율'을 함수가 얼마나 빠르게 증가하는가를 나타내는 것으로 설명할 때 쓰입니다.
예를 들어 T(n) = 2n^2 + 5n + 6 이라는 함수가 있다고 합시다. n이 점점 커진다면, 5n이나 6에 비해 2n^2 가 더욱 큰 비율로 늘어나고, 결국 n이 증가할 때 T(n)이 얼마나 빠른 속도로 증가하느냐는 것을 결정하는 것은 n^2입니다. 그렇기 때문에, 이 T(n)의 효율성을 Big-O notation으로 표현할 때
O(n^2) 라고 씁니다.
컴퓨터 프로그래밍으로 생각을 해 보겠습니다. n개의 숫자가 있는 정렬되지 않은 배열이 있고, 이 중에 가장 큰 숫자를 찾는 배열을 찾는 함수를 만든다고 생각해봅시다. 정렬이 되지 않았으므로 n개의 숫자를 일일이 체크해야하겠죠? 그렇다면 이 함수의 효율성은 그 숫자 n에 의해 좌우가 되므로 (10개면 10번을 체크해야하고, 20개이면 20번을 체크해야하죠) 이 함수의 효율은 O(n)이 됩니다.
반대로 정렬이 되어있는 배열에서 제일 큰 숫자를 찾는다고 합시다. 그럼 숫자가 몇 개든 상관없이 맨 뒤에 있는 숫자를 보면 되겠죠. n=10이든 n=20이든 걸리는 시간은 똑같습니다(constant). 이럴 땐 O(n)이 아니고 O(1)이겠죠.
이런 식으로 아래와 같은 Big-O notation들이 존재합니다. 보통 정렬할 때 걸리는 시간이라던가, 검색할 때 걸리는 시간등을 나타낼 때 가장 많이 나옵니다.
Big-O notation 은 알고리즘이 얼마나 오랜 시간이 걸릴지 측정하는 데 도움이 되며, 또 같은 분류에 속하는 알고리즘들은 대충 비슷한 시간이 걸릴 것이라는 암시도 해 줍니다.
Big-O, Big-Omega, 그리고 Big-Theta의 미묘한 차이에 대해 서술하려면 수학적인 정의를 내려야합니다. (위에선 쉽게 설명했는데, 정확한 정의를 내리면 조금 복잡해집니다)
1. Big-O Notation 정수 (integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f, g가 있다. 만약 |f(x)| ≤ C|g(x)|, x > k 를 만족시키는 상수 C와 k가 존재할 때, f(x)는 O(g(x)) 라고 한다.
2. Big-Omega Notation 정수 (integers) 또는 복소수(real numbers)를 복소수로 변환하는 함수 f, g가 있다. 만약 |f(x)| ≥ C|g(x)|, x > k 를 만족시키는 상수 C > 0와 k가 있을 때, f(x)는 Ω(g(x)) 라고 한다.
3. Big-Theta Notation 위와 같은 상황에서 f(x) 가 동시에 O(g(x)) 이고 Ω(g(x)) 일 때 f(x)는 Θ(g(x)) 라고 한다.
다시 말하면, Big-O Notation은 upper-bound, 즉 x가 증가할 수록 f(x) 보다 항상 스케일이 큰 g(x)를 찾는 것이고, Big-Omega Notation은 x가 증가할 수록 f(x)보다 항상 스케일이 작은 g(x)를 찾는 것이죠.
예를 들어보겠습니다.
f(x) = 8x^3 + 5x^2 + 7 이라고 합시다.
이것을 O(x^2) 라고 할 수 있을까요? 아닙니다. C가 아무리 크다고 해도, x가 무한으로 커지면 8x^3이 Cx^2 보다 커질 수 있기 때문이죠. 하지만 이것을 Ω(x^2) 라고 할 수 있을까요? 예, 그렇습니다. 바로 위와 같은 이유로, x가 무한으로 커지면 C가 아무리 커도 Cx^2보다 커질 수가 있기 때문이죠. 하지만 O(x^2)는 아니기 때문에 Θ(x^2)라고는 말할 수 없습니다.
그럼 x^3은 어떨까요? 잘 보시면 O(x^3)는 C가 8보다 큰 경우 성립하먀, Ω(x^3)는 C가 8과 같거나 작은 경우 성립한다는 것을 아실 수 있습니다. 그러므로 Θ(x^3)이라고도 할 수 있습니다.
쉽게 설명하자면, x^3을 주체(?)로 하는 함수가 f(x)의 아래와 위를 막고 있다는 얘기지요. 그러므로 x^3이 이 함수의 특성을 설명하기엔 적합한 겁니다.
이런 이유로, 알고리즘이나 함수, 또는 프로그램의 효율을 나타낼때는 Θ(Big-Theta)를 사용하는 것이 가장 강력한 힘(?)을 가지고 있다고 볼 수 있습니다.
조금 복잡한 설명이 되었지만 이 중 한 마디라도 도움이 되었으면 좋겠습니다. 덕분에 저도 복습할 기회가 되었군요. 그럼.... |
2010년 10월 21일 목요일
goog
계산의 복잡도 비교문제 big O notation
코드 재사용
http://kldp.org/node/58570
http://www.workingus.com/v2/gnu/bbs/board.php?bo_table=job&wr_id=21153&sca=Interview_QnA&page=20
http://zariski.egloos.com/508274
2010년 10월 15일 금요일
What does IBM joining OpenJDK mean for Java?
What does IBM joining OpenJDK mean for Java?
Oracle is not playing fair