알고리즘 수업 - 수행시간 1

24262번 : 알고리즘 수업 - 수행시간 1

• 문제
  

  //MenOfPassion 알고리즘
	
  MenOfPassion(A[], n) { //n이 입력받은 입력 크기이고
      i = ⌊n / 2⌋; // 입력 크기를 반을 나눈 것은 i변수에 저장한 후 
      return A[i]; # 코드1 // A[i] 번째의 값을 반환한다.
  }

• 이 코드는 딱 한번 실행된다 반복문이 없고 바로 반환함

• 즉, 어떤 수가 들어와도 무조건 1번 수행됨.

  둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

코드 1의 수행횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다 -> 최악의 경우를 상정하는 빅오표기법으로 시간복잡도를 나타내라는 것.

즉 코드1의 수행시간은 1번 뿐이기 때문에 수행시간은 O(1)

빅오 표기법_시간 복잡도
O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n)* – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.

따라서 그냥 1과 0을 줄바꿈해서 출력하면 됨.

public class Main {
    public static void main(String[] args) {
        //어떤 수가 들어와도 값은 똑같기 때문에 입력받지 않아도 됨
        System.out.println(1);
        System.out.println(0);
    }
}