시간복잡도

1. 시간복잡도

2. 공간복잡도

3. 입출력

 

우리는 한정된 자원을 갖고있다. 자원을 효율적으로 사용하려면 시간복잡도가 굉장히 중요하다.

메모리가 64GB 필요한 작업이면 구매하면된다. 하지만 구매해도 10일걸리는 작업이라면 10일이 소요된다.

시간복잡도 > 공간복잡도     중요하다.   

 

 

1. 시간복잡도

•  Big O표기법으로 표기.                     ex) O(1), O(N), O(N^3)......

• 코드를 보기전 시간복잡도를 보고 수행시간을 계산한후 제한시간안에 가능시 구현

• 최악의 경우 걸리는 시간을 나타냄

• 1억 = 1초  (실제로는 5억정도)            ex) O(N^3) = 1.25억  가능  -> O(1), O(N), O(N^2), O(N^3)

• 상수는 버린다. (큰수들이기 때문에 상수는 별 의미없음)     ex) O(3N) = O(N),   O(5) = O(1), 

• 두가지항일때 변수가 같으면 버린다.                              ex) O(N^2+N) = O(N^2)

• 서로다른 변수이면 냅둔다 (무엇이 큰지 모르기 때문)         ex) O(N+M)

 

다음은 코드를 통해 시간복잡도를 비교해보겠다.

int sum = 0;
for(int i=1; i<=N; i++)
    sum += i;
    
-----------------------------------------

int sum = (N+1)*N/2;

 

첫번째 코드는 sum=0이 한 번, int i=1이 한 번, i++이 N번, sum+=i가 N번 합쳐서 총 2N+2 번의 연산이 수행되었습니다.

Big-O 표기법으로 표현하면 2N+2 = O(N) 이므로, 첫번째 코드의 시간 복잡도는 O(N) 입니다.

 

두번째 코드는 (N+1)이 한 번, *N이 한 번, /2가 한 번, 대입 연산이 한 번 합쳐서 총 4번의 연산이 수행되었습니다.

Big-O 표기법으로 표현하면 4 = O(1) 이므로, 두번째 코드의 시간 복잡도는 O(1) 입니다.

 

시간복잡도가 O(N) > O(1) 이므로, 두번째 코드가 첫번째 코드보다 시간적인 측면에서 효율적입니다.

 

 

2. 공간복잡도

• 보통 메모리는 넉넉하기 때문에 메모리제한에 대한 걱정보다는, 대략적으로 공간을 얼마나 사용할지 예상할것.

• 공간을 가장 많이 사용하는것을 활용 = 배열 활용   (배열크기x자료형크기)

• 1초 = 381.469MB      (int a[10000][10000] 보통 1초 = 381MB)

   

 

3. 입출력

• 입력 

        :  Scanner, BufferedReader  

        ->  입력이 많을경우 BufferedReader 사용. (구현하는것이 복잡하나 애초부터 이것만써도 상관없음)

 

        ex) Scanner sc = new Scanner(System.in);

            BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));

 

함수별 10,000,000개의 숫자를 입력받을 때 대략적인 수행 시간

• 출력

         :  System.out, StringBuilder, BufferedWriter

 

                            빠르기 비교

        BufferedWriter  >  StringBuilder  >  System.out

 

 

 

---

       

<참고>

백준 사이트

cupjoo.tistory.com/97

barefoot-coder.tistory.com/9

medium.com/humanscape-tech/%EC%BD%94%EB%93%9C%EC%9D%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0-b67dd8625966