공간복잡도, 시간복잡도

[ttobaegi]

공간복잡도

• 주어진 메모리 공간을 고려해야한다.
• 스택은 계산하기 어려우므로 변수는 전부 전역변수로 하고 재귀함수는 1000번 이상 호출하지 않도록 한다.
• 변수별 메모리크기를 고려
• int 형은 4바이트, 1,000 = 4kb, 1,000,000 = 4mb, 10,000,000 = 40mb. 보통은 백만이하로 할당한다.
  • 2차원 배열일때는 [1000][1000] 이하로 한다. [10000][10000] 은 400mb 이기 때문이다.
• long long 은 8바이트, char, bool 은 1바이트 이다.

시간복잡도

• 주어진 입력을 토대로 루프나 재귀를 얼마나 쓸수있는지 추측해야 한다.
• 보통 1억번을 계산하는데 1초가 걸림
• Big-O 표기법을 이용해 O(~) 로 표현함
• O(1), O(N), O(NlgN), O(N^2), O(N^3), O(2^N), O(N!) 순으로 복잡도가 증가한다.
• 1초당 가능한 연산수(대략 외우기 쉽게)
• O(1)
  • 배열 접근
• O(N) : 1억
  • 단순계산, 배열구간합 계산시
• O(lgN) : 많이할수있다(1억을 넣어도 26.57 정도가 나옴)
  • N을 절반으로 계속 나눔
• O(NlgN) : 5백만
  • N을 절반으로 계속 나누지만 각 depth 별 계산합이 N을 유지할때, 머지소트
• O(N^2) : 1만
  • 2중 for 문
• O(N^3) : 500
  • 3중 for 문
• O(2^N) : 25
  • 부분집합(포함하거나 안하거나)
• O(3^N) : 15
  • 각 요소별로 상태가 2개 이상인 부분집합
• O(N!) : 11
  • 크기가 N 인 순열
• 재귀호출 계산방법
• T(N) = aT(N/b) + N^k*lg^p N
  • a 와 k 중에 어떤것이 더 영향이 있는가?, 한번 호출될때마다 k가 얼마나 영향이 있는가?
  • b 가 클수록 a는 영향력이 약해지고, k 는 강해진다.
  • a 와 b^k 의 관계가 존재
    • a > b^k : a 의 영향력이 크다. k 의 영향은 무시됨 -> N^logb a
    • a = b^k : 둘다 고려해 주어야 한다. -> N^logb a * lg^p+1 N
    • a < b^k : k 의 영향력이 크다. -> N^k * lg^p N
• MH 문제에서는 N^2 까지는 시간복잡도가 나올 수 있으나 그 이상은 안나오는 것으로 보인다.