1. 알고리즘 복잡도 계산 항목

1. 시간 복잡도: 알고리즘 실행 속도
2. 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함

• 알고리즘 시간 복잡도의 주요 요소

  → 반복문이 지배함

2. 알고리즘 성능 표기법

• Big O (빅-오) 표기법: O(N)
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용함
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문

3. 대문자 O 표기법

• 빅 오 표기법, Big-O 표기법 이라고도 부름
• O(입력)
  • 입력 n 에 따라 결정되는 시간 복잡도 함수
  • O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!)등으로 표기함
  • 입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
    • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)
• 단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
  • 표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다.
  • n이 1이든 100이든, 1000이든, 10000이든 실행을

    • 무조건 2회(상수회) 실행한다: O(1)

      if n> 10:
      	print(n)
      
      

    • n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)

      variable= 1
      for num in range(3):
      	for index in range(n):
      	  print(index)