시간복잡도 / 공간복잡도 / 빅오표기법(Big-O)

 

시간 복잡도는 속도, 공간 복잡도는 메모리 사용량을 나타냄

✔ 둘은 반비례하는 경향이 있지만, 항상 그런 것은 아님

✔ 보통 알고리즘의 성능은 “시간 복잡도”를 더 중요하게 고려

✔ 하지만, 메모리 제약이 있는 문제에서는 “공간 복잡도”도 고려

 

 

🔹 시간 복잡도(Time Complexity)

• 입력 크기(N)에 따라 연산이 얼마나 많이 수행되는지 나타냄

• O(빅오 표기법)으로 표현 (O(N), O(log N), O(N²), etc.)

 

🔹 공간 복잡도(Space Complexity)

• 입력 크기(N)에 따라 메모리를 얼마나 사용하는지 나타냄

• 변수, 리스트, 재귀 호출 등이 영향을 미침

 

 

❓빅오 표기법

주로 최악의 경우 시간 복잡도를 나타낸다.

아무리 많이 걸려도 최대 이 시간 안에는 끝난다는 것’을 나타낸다.

 

 

🔹성능 개선을 위해 시간복잡도를 줄이려면?

적절한 자료구조(배열, 스택, 큐.. 등) + 적절한 알고리즘(버블정렬, 선택정렬...등) 을 

선택해서 사용할 줄 알아야함.