자료구조와 알고리즘 인강 정리 : 시간복잡도

• 시간 복잡도 : 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간. 실행되는 n의 크기마다 실행되는 조작의 수를 나타낸다.
  
  좋은 알고리즘은 사용자의 요구에 따라 달라진다.(메모리 사용이 적은 것, 속도가 더 빠른 것) 일반적으로 알고리즘의 속도를 성능의 속도로 사용한다. 하지만 사용자마다 컴퓨터 사양이 다르기 때문에 시간으로 알고리즘을 평가하기에는 문제가 있음.
  따라서 알고리즘을 평가할 때는 코드에서 성능에 많은 영향을 주는 부분을 찾아 실행시간을 예측한다. 코드에서 성능에 많은 영향을 주는 부분은 반복문! 여러번 반복될때마다 느려진다.
  
  

배열에서 특정한 값을 찾는 코드

주어진 배열에서 10을 찾으시오. 1 3 5 8 10 --------------------------------------------------- 찾으려는 데이터가 배열의 어디에 있는지에 따라서 달라짐. -> 최선의 경우 한번에 찾음. -> big-Ω (빅오메가) -> 최악의 경우 배열의 길이만큼 걸린다. -> Big-O (빅오) - 가장많이 쓰임 -> 중간정도에 위치해있을 경우 배열의 길이 중간만큼 걸린다. -> Big-θ (빅세타) --------------------------------------------------- 배열의 데이터가 n개 있을 때 최악의 경우 n번만에 찾음 -> O(n) 으로 표현 -> 선형시간 알고리즘

 

• 알고리즘 성능 : O(1) -> O(logn) -> O(n) -> O(nlogn) -> O(n^2) -> O(2^n) -> O(n!)
  (오른쪽으로 갈수록 성능이 좋지 않다.)
  
  
• 빅오 표기법 : 입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것.
  ex) n^2 + 2n + 100의 성능을 가지는 알고리즘의 표현
   -> O(n^2)  -> 가장 계산에 많은 영향을 미치는 값만 표기한다.
  ex) 3n^2 + 300n의 성능을 가지는 알고리즘의 표현
   -> O(n^2)  -> 상수는 큰의미가 없으므로 제거한다.