[Do it 코테 자바편] 어떤 알고리즘으로 풀어야 할까?

• 시간 복잡도: 그냥 빅-오, 즉 최악일 때의 연산 횟수만 기억하면 됨 -> 어떠한 케이스라도 통과 못하면 안 되기 때문
• 어떤 코드의 시간 복잡도 파악
  • 상수는 무시한다. 즉 for문이 한 개 있으면 복잡도가 n이라 치자. for문이 3개 있어도 컴퓨터 입장에선 n이나 3n이나 도토리 키재기다. 그러니 무시한다.
  • 가장 많이 중첩된 반복문 수행 횟수가 기준이 된다: 즉 for문이 1억개 있어도, 이중 for문 하나를 못 이긴다는 소리다. 즉 복잡도는 n의 제곱이지, n의 제곱 + 1억*n이 아니란 소리다.
• 연산 횟수: 시간 복잡도 n에 데이터 크기 대입하면 됨

• 시간복잡도로 1. 문제 제한 시간에 맞는 알고리즘 선택할 수 있고 2. 내가 짜는 로직에서 복잡도 효율이 안 좋아 불통하는 부분을 찾아낼 수 있다

• 빠른 거부터 나열: logn > n > nlogn > n^2 > 2^n > n! - log1000000를 대하는 법: 밑이 2이다. 코테에서는 > log1000000이 x라면, 2의 x제곱이 백만이다 > 2의 10제곱이 1024, 즉 약 1000이다 > 2의 20제곱은 약 백만이다 > 따라서 log1000000은 약 20이다