[Algorithm](Big-O Notation), 시간복잡도, 공간복잡도

Big-O

Big-O는 알고리즘의 효율성을 나타내는 지표.
Big-O를 통하여 개선한 알고리즘이 빨라졌는지, 메모리를 많이 잡아 먹지는 않는지 등의 알고리즘의 성능을 판단한다.

시간복잡도

• 알고리즘의 수행시간이 얼마인지를 나타낸다.
  수행되는 연산의 수를 갖고 계산하며, 알고리즘에 중요하지 않은 값들은 최대한 무시한다.

• 반복문을 기준으로 입력 값(N)에 영향을 받는 핵심적인 코드가 어느 부분인지를 파악하고, N과 어떤 관계가 있는지를 파악하는 관점을 기르는 것이 중요. 연산이 많이 존재하더라도 하나로 취급해 big-O값을 구할 수 있음.

• 입력값(N)에 따른 실제 소요되는 시간이 big-O 결과와 다를 수도 있다.
  big-O는 단순히 증가하는 비율을 나타내는 개념으로, 데이터의 입력이 충분히 큰 것을 가정한다.
  알고리즘의 효율성은 데이터의 입력 값이 얼마나 큰지에 따라 영향을 받기 때문에 사소한 부분은 무시가 가능하다.

  상수항 무시

  O(2N) -> O(N)
  O(N2+2) -> O(N2)

  영향력이 없는 항 무시

  O(N2+N) -> O(N2)

• 자주 사용되는 시간복잡도

  O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!) < O(nn)

  • 오른쪽으로 갈 수록 시간복잡도가 큰 (수행시간이 긴) 알고리즘
    n의 값이 커지면 커질수록, 알고리즘의 수행시간이 급격히 길어진다.
    시간 복잡도를 낮출 수 있다면 프로그램에 큰 성능 향상 기대 가능

---

시간복잡도 예제

O(1) - 상수시간 (Constant time)

• 입력크기(n)에 상관없이 일정한 연산을 수행하면 시간복잡도는 O(1)이다.

int n=1000;
System.out.println(n);

• 얼마나 오래걸리는지 신경쓰지 X, 단지 일정한 시간이 걸린다.

int n = 1000;
System.out.println("Hey - your input is: " + n);
System.out.println("Hmm.. I'm doing more stuff with: " + n);
System.out.println("And more: " + n);

실행하는데 3배가 걸리더라도, n값에 의존하지 X

---

O(log n) - 로그 시간

• 상수 시간 알고리즘이 가장 빠름. 로그 시간은 그 다음으로 빠름
  일반적으로 이진검색의 시간복잡도
• 입력 로그에 비례하여 실행시간이 증가한다.

for(int i=1; i<n; i = i*2){
	System.out.println(i)
}

• (n=8) 이라면 결과 : log(8) = 3 (3번실행됨)

1
2
4

---

O(n) - 선형시간

• 로그 시간 다음으로 빠른 선형 시간 알고리즘

for(int i=0; i<n; i++){
	System.out.println(i)
}

• 입력 크기인 n에 대해서 선형적으로 증가함 (입력의 크기에 비례하여 직접 성장)

---

O(n log n) - N Log N 시간

for(int i=1; i<=n; i++){
	for(int j=1; j<n; j= j*2){
    	System.out.println(i + "and" + j)
	}
}

• ex) n=8 / 알고리즘은 8(i_for) * 3 (j_for) 로 24번 실행된다.

---

O(np) - 다항식 시간

for(int i=1; i<=n; i++){
	for(int j=1; j<=n; j++){
		System.out.println(i + "and" + j)
    }
}

• ex) n=8 / 위 알고리즘은 82 = 64회 실행됨. 또 다른 for 루프를 중첩할 경우 O(n3) 알고리즘이 됨!

공간복잡도

• 공간에 대한 개념으로 이 알고리즘이 공간을 얼마나 필요료 하는지를 나타냄
  시간 복잡도에 비해 중요도는 떨어지지만 신경 쓸 필요는 있음
• 크기가 N인 배열을 만든다 = 공간복잡도 O(N)
  크기가 NxN인 배열을 만든다 = 공간복잡도 O(N2)