[알고리즘] 시간 복잡도

안녕하세요? 주니하랑 입니다.

오늘은 알고리즘에서 시간 복잡도에 대해 공부 해 보도록 할 것이에요!

제가 푼 코드가 궁금하시다면? 주니하랑의 깃 허브에 관심을 주세요!

바로 시작 해 보겠습니다!

 

---

 

 

📌 Algorithm 복잡도 표현 방법

---

    📍 Algorithm 복잡도 계산

Algorithm에 복잡도에 대한 계산 방법은 왜 있는 것일까요?

그것은 바로 하나의 문제를 푸는 Algorithm이 너무나도 다양할 수 있기 때문인 것이에요.

예를 들어 정수의 절대값 (+1 = 1, -1 = 1)을 구하는 문제가 있다고 생각 해 볼게요.

어떤 사람은 정수값을 제곱한 값에 루트를 씌우는 방식으로 문제를 풀 수 있을 것이에요.

또 어떤 사람은 if문을 통해 해당 값이 정수인지 음수인지를 확인하고, 음수일 때만 -1을 곱하도록 할 수도 있는 것이에요.

위와 같이 다양하게 알고리즘이 나올 수 있기 때문에 어떤 것이 더 좋은지를 분석하기 위해 복잡도를 정의하고, 계산한답니다! 

 

 

 

 

    📍 Algorithm 복잡도 계산 항목

• 시간 복잡도 : Algorithm 실행 속도
• 공간 복잡도 : Algorithm 사용 Memory Size

여기서 가장 중요한 것은 시간 복잡도 인 것이에요! 요즘은 예전처럼 Memory 용량이 적지도 않고,크게 부담될 가격도 아니기 때문인 것이에요!

 

 

    📍 Algorithm 시간 복잡도 주요 요소

우리는 코딩을 하면서 여러가지 방법을 사용하게 되는 것이에요.

그 중 반복문이 시간 복잡도에 가장 큰 영향을 줄 수 있다고 해요!

입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배한답니다!

 

 

 

 

    📍 Algorithm 성능 표기법

         👉 Big O (빅-오) 표기법 : O(N)

이것은 알고리즘 최악의 실행 시간을 표기하는 기법인 것이에요.

가장 많이 사용되고, 일반적으로 사용된답니다!

아무리 최악의 상황이라도, 이 정도의 성능은 보장해야 한다이기 때문이라고 하네요!

 

         👉 Ω (오메가) 표기법 : Ω (N)

오메가 표기법은 알고리즘 실행 시간이 최고로 빠른 것을 표기하는 기법인 것이에요.

 

 

         👉 Θ (세타) 표기법 : Θ (N)

세타 표기법은 알고리즘 실행의 평균 시간을 표기하는 기법인 것이에요.