🎯시작 전 목표

1. 시간복잡도의 이해

💻Today I learned

✔ 시간복잡도의 이해

오늘은 평소에 잘 신경쓰지 않고 어렴풋이만 생각하던 시간복잡도에 대해 공부했다.
시간복잡도의 개념을 이해함으로써 앞으로 짜는 알고리즘을 개선해 보다 효율적인 코드를 짜기 위함이다.

시간복잡도는 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화한 것인데, 이름이 시간복잡도이면서 왜 시간을 계산하지 않고 연산만으로 판별하냐 묻는다면, 명령어의 실해시간은 컴퓨터의 하드웨어나 프로그래밍 언어에 따라 변차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.

입력값의 크기와 그 크기에 따른 함수의 증가량,즉 성장률을 중심으로 알고리즘의 실행 시간에 별로 중요하지 않는 상수와 계수들은 제거하면 이를 점근적 표기법이라 부른다.

시간 복잡도를 나타내는 데 사용하는 점근적 표기법은 세 가지가 있는데, 이는 다음과 같다.

• 오메가 표기법 (Big-Ω Notation)
  최상의 경우를 상정
• 세타 표기법 (Big-θ Notation)
  평균의 경우를 상정
• 빅오 표기법 (Big-O Notation)
  최악의 경우를 상정

평균의 경우를 상정한 세타 표기법을 사용하면 말 그대로 알고리즘의 평균 실행 시간을 구할 수 있겠지만,
프로그램을 짜는 입장에서는 불필요한 연산을 제거하고 알고리즘을 분석하는 것이 목적이기 때문에 최악을 상정한 빅오 표기법을 사용한다.

시간복잡도에서 중요하게 보는 것은 실행시간에 가장 큰 영향을 미치는 입력값(n)의 단위이다.

• 1 O(1) : 상수
• 3n O(n) : n이 가장 큰 영향을 미침
• 5n²+3 O(n²) : n이 가장 큰 영향을 미침

시간복잡도의 문제해결단계는 다음과 같다.

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

• O(1) : 상수

  입력과 관계없이 동일한 복잡도가 유지된다.

  System.out.println("Hello World!");    

• O(log n)

  입력 크기에 따라 처리 시간이 증가한다.

  	public int Binary(int[] arr, int item, int f=0, int l )
      {
      	if(last==0) last = arr.length;
          int point = (l-f)/2 + f;
  
          if(arr[point]==item) return point;
          else if(arr[point]>item) return Binary(arr, item, f, point);
          else return Binary(arr, item, point, l);
      }

• O(n) : 선형

  입력에 따라 처리시간 혹은 메모리증가가 선형적으로 증가한다.

  for(int i : arr.length)
  {
  	System.out.println(i);
  }

• O(n log n)

  입력 크기에 따라 처리 시간이 증가한다.
  코드는 길이가 있는 관계로 적지 않지만 나중에 작성할 정렬에서 확인이 가능하다.

• O(n²) : Square

  반복문이 2번 있는 케이스에 해당한다.

  for(int i=0;i<a.length;i++)
  {
  	for(int j=0;J<a[a.length].length;j++)
      {
      	System.out.println(a[i][j]);
      }
  }