Algorithm 공부 #01 - 시간 복잡도와 디버깅

 

Algorithm 공부 #01 - 시간 복잡도와 디버깅

 

시간 복잡도

 

 ● C++에서는 1억 번의 연산을 1초의 수행 시간으로 예측한다

 ● 시간 복잡도

      → 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도로 총 3가지의 표기법이 있음

           1. 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법  

           2. 빅-세타(      : 보통일 때(average case)의 연산 횟수를 나타낸 표기법

           3. 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

           ※ 코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하기

  ● 시간 복잡도 도출 기준

       1. 상수는 시간 복잡도 계산에서 제외한다.

       2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

간단한 예제

 https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 ● 백준 2751번 수 정렬하기2

    → N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하는 문제

    → N의 범위는 1≤N ≤1,000,000, 시간 제한은 2초

         기본적인 정렬 알고리즘으로는 버블 정렬(O(N^2)), 삽입 정렬(O(N^2)), 병합 정렬(O(n log n))등이 있음 

         연산 횟수는 1초에 1억번 연산을 기준으로 하는데, 만약 버블 정렬이나 삽입 정렬을 사용할 경우에는

         연산 횟수가 1,000,000 * 1,000,000 > 200,000,000으로 부적합한 알고리즘이고, 병합 정렬일 시에는

         연산 횟수가 1,000,000 * log(1,000,000) = 약 20,000,000 < 200,000,000으로 적합하다는 결론이 나옴

         

 

디버깅

 ● 논리 오류를 찾아 바로잡는 과정

 ● 디버깅 방법

    1. 코드에서 디버깅하고자 하는 줄에 중단점을 설정하기(여러 개 설정 가능)

    2. IDE의 디버깅 긴으을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며, 이 과정에서

        추적할 변숫값도 지정가능

    3. 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있음

  ※ 의도치 않게 정답으로 음수를 출력한다면 변수 범위 초과를 의심해 보기!

 

  디버깅 활용 사례 

#include<iostream>
#include<cstdlib>
#include<climits>
using namespace std;

int main(){

int testcase;
cin>>testcase;

int answer=0;
int A[100001] = {0};
    
    for(int i=1; i<10001; i++){  // 배열의 인덱스 범위만큼 제대로 할당하였는지
    	A[i]= rand() * 100;   
    }  
    
    for(int i=1; t<testcase; t++){
    	int start, end;
        cin>>start>>end;
        
        for(int i= start; i<=end; i++){
        	answer += A[i];  /* answer의 자료형의 범위가 적절한지(A[i]의 값을 계속 더하다 보면
                              int형의 범위를 넘어갈 수 있음 */
        }
        cout<<testcase<<" " <<answer; //출력하는 변수를 혼동하지 않았는지
    }
}