알고리즘 연습 사이트
Day 25:Running Time and Complexity
알고리즘의 복잡성이나 성능을 따져볼 때 asymptotic notation(점근 표기법)을 사용하여 나타낸다.
아무리 성능이 느린 알고리즘도 CPU가 좋다면 느린 CPU에서 성능이 좋은 알고리즘보다 빠를 수 있다.
때문에 이러한 기계의 성능과는 독립적으로 알고리즘 그 자체에 대한 성능을 알아보기 위해 점근 표기법을 사용한다.
$f(n)$은 내가 만든 알고리즘을 나타내고 $g(n)$는 어떤 점근적으로 도달되는 함수를 나타낸다.
점근적으로 도달될 때 특징이 있는데, 내가 만든 알고리즘이 성능의 최소치보다는 항상 위이거나, 최대치보다는 항상 아래일 수 있다.
그러한 특징을 세타나 빅오 등으로 표기하는 것이다.
1. $\Theta$ notation
세타 표기법, $f(n) = \Theta(g(n))$
즉 $f(n)$이 $g(n)$사이에 있기 때문에 $f(n) = g(n)$이라고 봐도 된다.
$ c1·g(n) ≤ f(n) ≤ c2·g(n) $
2. Big-Ο notation
빅 오 표기법, $f(n) = O(g(n))$
$f(n) ≤ g(n)$
3. $\Omega$ notation
$f(n) ≥ g(n)$
오늘 문제는 소수를 찾는 알고리즘을 만들어보는 것이다.
어떠한 $n$이 소수인지 아닌지 판별하는 방법은 찾고자하는 수를 $2$ 부터 $\sqrt n$까지 $1$씩 증가시키면서 나누면서 나누어 떨어진다면 소수가 아니고 나누어 떨어지지 않는다면 소수이다.
이 원리 혹은 증명은 여기서 다루지 않는다. 일단 이 공식만 알면 코드 작성은 쉽다.
아래 코드의 소스 알고리즘은 $O(\sqrt n)$ 의 복잡도를 가진다.
$g(n)$이 $\sqrt n$인데 최대 $\sqrt n$ 수까지 나누어봐야 소수인지 아닌지 알아낼 수 있기 때문이다. $\sqrt n$ 보다는 복잡도가 높아질 수 없으므로 빅 오 표기법으로 나타낼수 있다.
어떠한 $n$이 소수인지 아닌지 판별하는 방법은 찾고자하는 수를 $2$ 부터 $\sqrt n$까지 $1$씩 증가시키면서 나누면서 나누어 떨어진다면 소수가 아니고 나누어 떨어지지 않는다면 소수이다.
이 원리 혹은 증명은 여기서 다루지 않는다. 일단 이 공식만 알면 코드 작성은 쉽다.
아래 코드의 소스 알고리즘은 $O(\sqrt n)$ 의 복잡도를 가진다.
$g(n)$이 $\sqrt n$인데 최대 $\sqrt n$ 수까지 나누어봐야 소수인지 아닌지 알아낼 수 있기 때문이다. $\sqrt n$ 보다는 복잡도가 높아질 수 없으므로 빅 오 표기법으로 나타낼수 있다.
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//Read input from STDIN.
int count = sc.nextInt();
int [] arr = new int[count];
for(int i = 0 ; i < count;i++){
arr[i] = sc.nextInt();
}
for(int k= 0 ; k < count ; k++){
if(isPrime(arr[k])){
System.out.println("Prime");
}else{
System.out.println("Not prime");
}
}
}
public static boolean isPrime(int n){
if(n == 1){
return false;
}
if(n == 2){
return true;
}
for (int i = 2; i<=Math.sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
댓글 없음:
댓글 쓰기