알고리즘 복잡도 표현 방법 🤔

어떤 문제를 풀이하는데 완벽하게 똑같은 코드는 존재하지 않으나 어떤 풀이가 좋은 풀이냐 ? 라는 기준을 표현하는 방법을 익히는 것이다.

→ 어느 알고리즘이 더 좋은지를 분석하기 위해서 복잡도 라는 것을 정의 해 알고리즘 간에 비교를 한다.

어떻게 정의를 할까? 🤔

• 시간 복잡도⇒ 알고리즘의 실행 속도를 의미한다.
• 공간 복잡도⇒ 알고리즘이 사용하는 메모리 사이즈를 의미한다.

(사실상 공간 복잡도 보다는 시간 복잡도로 평가하는 경우가 많다.)

시간 복잡도는 어떻게 계산할까? 🤔

결과적으로는 반복문이 지배한다.

프로그래밍은 변수/조건문/반복문 으로 이루어져 있다.

이중 변수/조건문을 사용한다 해서 프로그램 성능을 좌우하진 않으나 반복문은 영향을 끼친다.

결과적으론 시간 복잡도에는 반복문이 큰 영향을 끼친다.

알고리즘 성능 표기법 🤔

• Big O (빅-오) 표기법 : O(n)
  • 알고리즘 최악의 실행 시간을 표기한다. (최악의 경우에 이 프로그램이 얼마의 시간이 걸릴것인가? 를 정의한다.)
  • 가장 많이 사용된다.
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문이다.
• 오메가 표기법 : Ω(n)
  • 오메가 표기법은 알고리즘 최상의 실행 시간을 표기한다.
• 세타 표기법 : Θ(n)
  • 세타 표기법은 알고리즘 평균 실행 시간을 표기한다.

계산 표기는 최악의 시간인 빅오 표기법을 중심으로 익히면 된다.

빅 오 표기법 🤔

• 무조건 상수회 를 실행한다면 ? ⇒ O(1)
• 이중 반복문이지만 상위 (밖의 반복문이) 상수로 반복한다면 ? ⇒ O(n) (상수는 안쪽 반복문의 ~번(n)이 무한대가 되면 큰 의미가 없어진다.)
• 삼중 반복문이지만 상위가 상수번 반복한다면? O(n^2)

참고 → log n 의 베이스는 2-log2n 이다.

실질적으로 프로그램의 각각의 실행 속도는 다를 수 있지만 시간복잡도 비교는 이런식으로 가능하게 된다.

예제로 알아보자. 🤔

반복문으로 1부터 N까지의 합을 구하는 함수 ?

• 하나의 반복문이 사용된다.

하나의 반복문이기 때문에 무조건 상수회를 실행한다. 따라서 **O(1)**이라고 할 수 있다.

반복문으로 1부터 N까지의 합을 구하고 각 수 마다 또 다시 N까지의 숫자를 한번 더 더 한다면?

• 상수로 반복하는 반복문 안에 또 다른 반복문이 존재한다.

이중 반복문이지만 상위 반복문이 상수회 반복하기 때문에 **O(n)**이라 할 수 있다.

하지만 이중 반복문과 또 하나의 반복문이 나온다면?

3회 반복하는 반복문 안에 n번 실행하는 반복문이 2개가 존재하고 그 다음은 5회 반복하는 반복문안에 n번 실행하는 반복문이 하나가 존재한다면?

3n^2 + 5n 으로 표기하지 않고, 가장 높은 차수가 제일 중요하고 상수 자체는 큰 영향이 없기 때문에 빅오 표기법으로는 O(n^2)로 표기한다.

느낀점 🤔

• 시간복잡도에 대한 개념을 전혀 이해하지 못하고 알고리즘 문제를 풀이했었는데 굉장히 쉽게 이해가 되었습니다.
• 앞으로 알고리즘 문제를 풀때 시간초과가 날 수 있는 상황을 미리 예상하고 최적의 답을 입력할 수 있을것 같습니다.
• 뿐만 아니라 개발 할때도 적절한 상황에 적합한 코드를 작성하여 성능에도 신경 쓸 수 있겠구나 하는 생각이 들었습니다.🤔