【알고리즘】시간복잡도와 공간복잡도, 표기법

안녕하세요 【키보드 워리어】
블로그 방문자 여러분, 안경닦이입니다.

---

오늘은 알고리즘 에 대해 알아보겠습니다.

 

---

알고리즘이란

서론:알고리즘(algorithm)은 수학과 컴퓨터과학에서

어떠한 문제를 해결하기 위해 정해진 일련의 절차입니다.

 

알고리즘은 전산학, 컴퓨터과학, 언어학 등에서

핵심적인 과목으로, 적절한 자료구조와 적절한 알고리즘이 있다면

좋은 소프트웨어가 됩니다.

 

그러므로 알고리즘에 관한 내용들은 컴퓨터의 전 분야에서 기본적이며, 필수적이라고 할 수 있는데요.

 

앞으로 알고리즘으로 정렬, 탐색, 그래프 등주요 알고리즘 설계 및 분석 방법을 포스팅하도록 노력하겠습니다.

 

문제 해결들을 위해 여러 동작과 반복들을 정리하면

시간 복잡도와 공간 복잡도를 어느 정도 이해해볼 수 있습니다.

 

알고리즘의 수행 시간을 분석할 때 복잡 도는 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킵니다. 알고리즘을 취해 시간을 정량화하는 것이라고 할 수 있습니다.

 

---

 

시간 복잡도

시간 복잡도는 알고리즘을 실행시켜 완료할 때까지 걸리는 시간을 의미합니다.

수행되는 단위 연산의 수행 횟수의 합으로 표현합니다.

 

 

 

시간 복잡도를 판단할 때 우리는 각 1줄로 이루어진 코드를 1번의 연산이 필요하다고 정의합니다.

비교 연산자 거나, 대입 연산의 경우가 이러합니다.

 

 

 

※지정 연산자와 비교 연산자에 대한 정리 글을 확인하고 싶다면 아래 포스트 글을 참고하시면 감사하겠습니다!

2022.07.07 - [JAVA 완전정복!!/Jshell] - 【JShell】 if문 연습 및 지정 연산자와 비교 연산자 차이, 블록 활용

【JShell】 if문 연습 및 지정연산자와 비교연산자 차이, 블록 활용

 

 

 

 

 

중요한 점은 시간 복잡도에서 배열(array, string)을 계산할 때입니다.

 

 

자료가 많으면 많아질수록 계산해야 하는 횟수도 복잡해져서 배열은

1번의 연산이라고 생각하지 않기 때문입니다.

 

 

 

array와 string를 보통 N이라고 표현합니다.

이 코드들은 시간 복잡도에서 많은 비중을 차지하는데요.

 

 

 

공간 복잡도는 알고리즘에서 사용되는 메모리의 양을 나타냅니다.

저장하는 데이터의 양이 1개의 공간을 사용한다고 할 수 있습니다.

 

 

 

하지만, 대부분의 알고리즘의 성능이 시간에 의해 결정되며, 공간에 연연하지는 않습니다.

 

점근 표기법

알고리즘의 효율성을 평가하기 위해서 점근 표기법을 사용하는데

점근 표기법의 종류에는 빅오( BIG - O)표기법, 빅 오메가(BIg- 오메가) 표기법이 있습니다.

 

 

 

빅오 표기는 최악의 성능이 나올 때 연산량 의미하고, O(N)으로 표기합니다.

빅 오메가는 최선의 성능이 나올 때 연산량 의미하며, Ω(1)으로 표기합니다.

 

 

 

제가 왜 최악의 성능이 나온 빅오 표기를 먼저 설명했을까요?

그것은 모든 알고리즘에서 최선의 경우보다 최악의 경우를 산정하기 때문입니다.

 

 

 

표기의 예를 잠깐 들어볼까요?

array element [n]의 길이만큼 연산을 실행하는 코드가 있을 때

변수 number와 element 배열을 비교해야 한다고 가정할 경우

 

 

 

N * 1의 시간 복잡도를 가집니다.

array는 N으로 표기하며  이를 1번 수행하기 때문입니다.

 

그런데 입력값인 number가 element 배열의 값들 중에서

바로 앞에서 값을 찾아낸 경우와 맨 뒤에서 값을 찾을 경우가 있지 않겠습니까?

 

 

 

이런 경우 시간 복잡도를 빅오 표기법으로 하면 O(N)으로, 빅 오메가 표기법으로는 Ω(1)로 표현할 수 있는 겁니다.