간단한 시간복잡도 공간복잡도

시간복잡도

• 1초당 반복문 수행 횟수가 1억(10⁸)을 넘어가면 시간 제한을 초과할 가능성이 있다
• 1초가 걸리는 입력의 크기

• O(1)
• 한 번에 알 수 있다
• O(lgN)
• 반씩 줄여 나간다. 이분 탐색
• O(N) : 1억
• 1 개의 for 문
• O(NlgN) : 5백만
• O(N^2) : 1만
• 2 개의 for 문
• O(N^3) : 500
• 3 개의 for 문
• O(2^N) : 20
• 
  
• O(N!) : 10
• 순열

공간복잡도

• 재귀 호출에 따른 스택 크기는 계산이 어려우니 1 만번을 초과하지 않도록 한다

• 2 차원 배열인 경우에 크기 계산에 조심

• int 형 [10000][10000] 은 대략 400 MB

• Bit 기반 자료크기
• 1 << 0 =>      1
• 1 << 1 =>      2
• 1 << 2 =>      4
• 1 << 3 =>      8
• 1 << 4 =>     16
• 1 << 5 =>     32
• 1 << 6 =>     64
• 1 << 7 =>    128
• 1 << 8 =>    256
• 1 << 9 =>    512
• 1 << 10 => 1024
• 1 << 11 => 2048
• 1 << 12 => 4096