01-1 시간 복잡도 표기법 알아보기

알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다.

시간 복잡도 유형

• 빅-오메가: 최선일 때 연산 횟수를 나타낸 표기법
• 빅-세타: 보통일 때 연산 횟수를 나타낸 표기법
• 빅-오: 최악일 때 연산 횟수를 나타낸 표기법

O(logn), O(n), O(nlogn), On^2), O(2^n), O(n!)

01-2 시간 복잡도 활용하기

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

연습문제 000)

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

import java.util.Scanner;

public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int roof = count;
        int [] num = new int[count];
        for(int i = 0; i<count; i++){
            num[i] = sc.nextInt();
        }
        for(int i = 0; i<count-1; i++){
            for(int j = 0; j< roof-1; j++){
                if(num[j]>num[j+1]){
                    int a = num[j];
                    num[j] = num[j+1];
                    num[j+1] = a;
                }
            }
            roof--;
        }
        for(int i = 0; i<count; i++){
            System.out.println(num[i]);
        }
    }
}

02-1 디버깅은 왜 중요할까?

디버깅 하는 법