Hackerrank Day 25 Running Time and Complexity

알고리즘 연습 사이트

www.hackerrank.com

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) = \Omega(g(n))$
$f(n) ≥ g(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;
    }
}