99클럽 코테 스터디 33일차 TIL + Big-O 표기법(1)

학습 키워드

- Big-O 표기법

 

공부한 내용

시간복잡도**(Time Complexity)**

• 알고리즘이 실행될 때 필요한 ‘입력값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미한다.
• 즉, 입력 값이 커질수록 알고리즘의 수행 시간이 어떻게 증가하는디에 따른 지표를 의미한다.
• 시간 복잡도는 ‘빅오 표기법(Big-O notation)’를 통해 표현하며, ‘수치가 작을수록 효율적인 알고리즘’을 의미한다.

공간 복잡도(Space Complexity)

• 알고리즘이 실행될 때 필요한 ‘메모리의 공간의 양’을 의미한다.
• 즉, 알고리즘의 효율성을 판단하는 데 사용되며 일반적으로 메모리 사용량이 적을수록 더 효율적인 알고리즘이라고 할 수 있다.
• 공간 복잡도는 일반적으로 알고리즘의 시간 복잡도와 함께 고려되며 알고리즘이 실행되는 환경에 따라 달라질 수 있다. 예를 들어, 일부 알고리즘은 실행될 때 추가적인 메모리를 필요로 하지 않지만 다른 알고리즘은 입력 데이터의 양에 따라 필요한 메모리 공간이 증가할 수 있다.
• 따라서 알고리즘을 설계할때에는 시간 복잡도와 공간 복잡도를 함께 고려해야다.

Big-O 표기법

• 알고리즘의 입력 크기에 대해 수행 시간이 어떤 방식으로 증가하는지를 표기하는 것으로 최악의 경우의 시간 복잡도를 의미한다.
• 빅오 표기법을 통해 성능을 개선하거나 적절한 알고리즘을 선택할 수 있다.

최악의 경우의 시간 복잡도란?

• 알고리즘이 입력 크기에 따라 가장 오래 걸리는 경우를 의미한다.
• 이를 분석함으로써 알고리즘을 설계할 때 최악의 성능을 예측하고 최악의 경우에도 어느 정도의 실행 속도를 보장함을 확인한다.

점근적 분석

• 시간 복잡도를 고려하기 위해서, 입력값의 변화에 따라서 실행되는 연산의 횟수와 시간을 비교한다.
• 데이터 입력값이 작은 문제
  • 알고리즘의 효율성이 중요하지 않고, 비효율적이어도 무방하다.
• 데이터 입력값이 충분히 큰 문제
  • 알고리즘의 효율성이 중요하고, 비효율적인 알고리즘은 치명적이다.
• 즉 입력값이 커짐에 따라서, 소요되는 시간을 최소화하는 것이 목적이다.

이러한 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라고 한다.

ex) 함수의 극한

어떠한 문제 해결을 위한 알고리즘의 성능분석을 할 때, 다양한 요소에 의해 비교 결과가 항상 일정하지 않을 수 있다. 이를 효과적으로 해결하는 방법이 점근적 분석이며, 이는 주어진 데이터의 크기를 기준으로 수행시간 혹은 사용공간이 얼마나 되는지를 객관적으로 비교할 수 있는 기준을 제시해준다.

---

점근적 표기법

Asymptotic Notation

점근적 표기법은 시간복잡도를 나타내는데 사용된다.

최상의 경우 : Big-Ω Notation (빅-오메가)

◼ 최상을 고려하는 Ω( g(n) ) : 하한 점근

적어도 g(n)의 비율로 증가하는 함수
f(n) = Ω(g(n))으로 보는 직관적 의미 :
	f는 g보다 느리게 증가하지 않는다.

: 최선의 시나리오로 최소 이정도 시간이 걸린다.

Notation (스몰오메가)

◼ ω( g(n) ) : 여유 있는 하한 점근, o( g(n) )과 정확히 대조됨

f(n) = ω(g(n))으로 보는 직관적 의미 :
	f는 g보다 빠르게 증가한다.

: 주어진 알고리즘이 아무리 좋아도 비교하는 함수보다 좋지 못하다.

평균의 경우 : Big-θ Notation (빅-세타)

◼ 중간, 평균 정도의 θ( g(n) ) : 점근선 상한선과 점근적 하한선의 교집합

g(n)의 비율로 증가하는 함수
f(n) = θ(g(n))으로 보는 직관적 의미 :
	f는 g와 같은 정도로 증가한다.

: 주어진 알고리즘이 아무리 좋아지거나 나빠지더라도 비교하는 함수의 범위 안에 있다.

o Notation (스몰오)

◼ O( g(n) ) : 여유있는 상한 점근

f(n) = o(g(n))으로 보는 직관적 의미 :
	f는 g보다 느리게 증가한다.

: 주어진 알고리즘이 아무리 나빠도 비교하는 함수보다 좋다.

최악의 경우 : Big-O Notation (빅-오)

◼ 최악의 경우 O( g(n) ) : 상한 점근

기껏해야! g(n)의 비율로 증가하는 함수
f(n) = O(g(n))으로 보는 직관적 의미 :
	f는 g보다 빠르게 증가하지 않는다.
    (상수 비율의 차이는 무시)

: 주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다.

---

 

 

 

참고 자료

- https://adjh54.tistory.com/186#3)%20%EB%B9%85%EC%98%A4%20%ED%91%9C%EA%B8%B0%EB%B2%95(Big-O%20notation)-1

- https://velog.io/@frombozztoang/Java-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84Time-Complexity-Big-O