알고리즘 강의를 듣다 보면 Big-O, O(n) 이런 표기가 계속 나오는데 솔직히 아직도 감이 잘 안 옵니다. 코드 짜서 돌리면 잘 돌아가는데 왜 굳이 이런 걸 따지는 건가 싶기도 하고요.
대충 이런 식으로 나오던데요.
O(1) 해시 조회, 배열 인덱스 접근
O(n) 반복문으로 전체 한 번 훑기
O(n^2) 이중 반복문 (전체를 매번 다시 훑음)
제가 궁금한 건 이겁니다. 실행 시간(초)을 재는 것도 아니고 정확한 연산 횟수도 아닌 것 같은데, 이 표기가 정확히 무엇을 나타내는 건가요? 상수는 왜 무시하고(2n도 그냥 O(n)이라던데), n^2 + n 같은 것도 왜 O(n^2)로 뭉개는지 모르겠어요.
데이터가 적을 땐 O(n^2)여도 잘만 돌아가는데 왜 이렇게까지 중요하게 다루는지, 실무에서 이게 왜 문제가 되는지 같이 설명해주시면 감사하겠습니다.