시간복잡도(Time Complexity)

  • 알고리즘이 문제를 해결하는 데 걸리는 시간을 측정하는 것으로 입력 크기의 함수로 표현.
  • 'Big O' 표기법을 사용하여 표현하며 O(1), O(n), O(n²) 등이 있음.
    O(1)은 상수 시간 알고리즘이며 입력 크기에 관계없이 일정한 시간 내에 문제 해결이 가능.
    O(n)은 선형 시간 알고리즘이며, 입력 크기에 비례하여 실행 시간이 증가.
    O(n²)는 이차 시간 알고리즘이며, 입력 크기의 제곱에 비례하여 실행 시간이 증가.
  • 알고리즘의 시간 복잡도가 낮을수록, 즉 O(1)이나 O(log n) 등의 복잡도를 가질수록 실행 시간이 더 짧아짐.

공간복잡도(Space Complexity)

  • 알고리즘이 문제를 해결하는 데 필요한 메모리 공간의 양을 측정하는 것으로 입력 크기의 함수로 표현.
  • 'Big O' 표기법을 사용하여 표현하며 O(1), O(n), O(n²) 등이 있음.
    O(1)은 고정 크기의 메모리만 사용하는 알고리즘으로 입력 크기에 관계없이 메모리 사용량이 일정.
    O(n)은 입력 데이터 크기에 비례하여 메모리 사용량이 증가하는 알고리즘.
    O(n²)는 입력 데이터 크기의 제곱에 비례하여 메모리 사용량이 증가하는 알고리즘.
  • 알고리즘의 공간 복잡도가 낮을수록, 즉 O(1)이나 O(log n) 등의 복잡도를 가질수록 메모리 사용량이 적어짐.

결론

  • 시간 복잡도와 공간 복잡도는 알고리즘의 효율성을 평가하는 중요한 요소.
  • 시간 복잡도가 중요한 이유는 알고리즘이 실행되는 시간이 사용자 경험과 연결되기 때문. 느린 알고리즘은 사용자가 결과를 기다리는 동안 대기하는 시간이 늘어나므로 사용자가 애플리케이션을 떠나거나 프로그램의 실행을 중단할 가능성이 큼. 시간 복잡도가 높은 알고리즘은 일반적으로 실제 애플리케이션에서 사용하지 않는 것이 좋음.
  • 공간 복잡도가 중요한 이유는 알고리즘이 사용하는 메모리의 양이 많을수록, 애플리케이션의 성능이 저하될 가능성이 커 메모리 사용량이 큰 알고리즘은 일반적으로 시스템 전체의 성능을 감소시키며, 특히 메모리가 제한된 장치나 환경에서는 문제를 야기할 수 있음.
profile
응애 나 아기 개발자

0개의 댓글

Powered by GraphCDN, the GraphQL CDN