왕초보의 알고리즘 정렬 종류 파헤치기 1 (자료구조, 시간 공간 복잡도)

학교에서 push swap을 하는 친구들이 과제를 수행하는 것을 보니 각자 다른 알고리즘 종류를 사용하고 있었고, 어떤 친구는 초반에 잘못된 알고리즘을 골랐다며 땅을 치며 후회하는 모습을 보기도 했다. 내 성격상 프로젝트를 진행하기에 앞서서 알고리즘 종류를 모두 알아보고 선택해 보겠다.

 

알고리즘이란 단어를 들으면 괜히 어렵고 박사님들만 할 수 있을 것 같은 느낌이 든다. 알고리즘은 AI를 다룰 때 많이 나온다고 생각했는데, 이번에 공부를 하면서 의외로 간결하고 깔끔한 설명들에 무거웠던 마음(?)이 한시름 놔졌다. 나는 push swap을 하기 전에 알고리즘 공부를 하고 싶어서 한국에 갔을 때 <쏙쏙 들어오는 인공지능 알고리즘>이란 책을 샀다. 인터넷의 여러 자료들과 이 책을 참고해서 블로그를 작성해 본다.

 

---

알고리즘이란?

일단 알고리즘의 의미를 알아보자.

알고리즘은 어떠한 문제를 해결하기 위해 정해진 일련의 절차.
계산을 실행하기 위한 단계적 절차를 의미하기도 한다.

알고리즘의 특성

알고리즘은 컴퓨터에서 사용되는 것으로 많이 알고 있지만 사실 알고리즘은 컴퓨터가 등장하기 한참 이전부터 등장해 수학자들이 문제를 풀기 위한 수학적 공식, 즉 알고리즘등을 개발해서 손으로 문제를 해결하기도 했다!

 

요즘 일상생활에 쉽게 사용하는 알고리즘들은, 문제에 대한 판단을 점진적으로 반복해 합리적인 결론을 이끌어내는 사고방식을 도식화한 게 알고리즘이라고 대체적으로 불린다. 예를 들어 유튭이나 인스타그램은 우리의 활동을 분석하여 콘텐츠를 추천하고, 다양한 게임과 수학 공식, 생물학, 금융, 블록체인 등에서 많이 사용하고 있다.

---

자료구조 (Data Structure)

자료구조는 컴퓨터의 세계에서 효율적인 데이터의 접근 및 수정을 가능하게 하는 자료의 조직, 관리, 저장을 의미한다.  더 정확히 말해서, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 해 주기 때문에 이 파트도 그냥 넘어갈 수 없다!

 

자료구조의 포스팅을 보고 오자!

자료구조 (Data Structure) 기본 이해하기

---

시간복잡도 (Time Complexity)

시간 복잡도는 보통 알고리즘의 정렬 이름 옆에 어려운 수학용어로 쓰여있는 것들이다. 처음에 이게 왜 있을까.. 하고 궁금해했었다. 아래의 내용은 내가 읽고 있는 책 <쏙쏙 들어오는 인공지능 알고리즘>에서 부분 발췌한 내용이다.

 

프로그램을 작성할 때 함수는 연산으로 구성되며, 전통적인 컴퓨터의 동작 방식으로 인해 각각의 함수에 필요한 처리 시간이 서로 다르다. 더 많은 계산이 필요할수록 함수를 처리하기 위한 비용이 커지는 것이다.

빅 오 표기법 Big O notation은 함수나 알고리즘의 복잡도를 설명하기 위해 사용하는데,
입력 크기가 커짐에 따라 필요한 연산 횟수를 모델링한다. 

 

다음은 점근 표기법(asymptotic notation, 대문자 O로 표기할 수 있는 방법)에 대한 몇 가지 예와 그것과 관련한 복잡도다.

 

💡만약 Hllo World를 화면에 출력하는 단일 연산이라면?

👉 이 작업은 단일 연산이고, 계산 비용은 O(1)이다. 단순한 입출력 작업.

 

💡목록에 있는 항목들을 출력하는 함수라면?

👉 연산의 횟수는 목록 내의 항목 수에 따라 달라지고, 이때의 비용은 O(n)이다.

 

💡한 목록의 각 항목과 다른 목록의 각 항목을 비교하는 함수라면?

👉 이 연산의 비용은 O(n²)이다.

 

이렇게 원하는 결과와 자료의 수에 따라서 복잡와 시간이 늘어나기 때문에 수학적으로 얼마나 시간이 걸리는지 빅 오 표기법을 사용해서 간단하게 표현한 것이다! 아래의 그래프를 보자.

수학 공식이 복잡해질수록 시간이 늘어나요!

O표기법에 상통하는 정렬 방법들은 아래와 같다.

가능성이 많아질 수록 시간이 늘어난다.

이렇게 시간과 자료에 따라서 복잡도가 달라진다. 하지만 많은 

• 상수시간(constant time) : 단순하게 숫자 혹은 n으로 표현된 복잡도. 만약 T(n)이 O(어떤 상수값)이라면, 'T(n)은 O(1)이다'
• 로그시간(Logarithmic time) : 만약 T(n) = O(log n)이라면, 이 알고리즘은 로그 시간이 걸린다고 말할 수 있다.
• 선형 시간 (Linear time) : 만약 시간복잡도가 O(n)이면, 이 알고리즘은 O(n) 시간 혹은 선형 시간을 갖는다고 말할 수 있다.
• 서브-선형 시간 (Sub-linear time) : 만약 T(n) = o(n)이면, 이 알고리즘은 서브-선형시간 동안 작동된다고 말할 수 있다.
• 선형 로그 시간 (Linearithmic time) : 만약 T(n) = O(n log n)이라면, 알고리즘은 선형로그 시간 동안 실행된다고 말할 수 있다.
• 서브-이차 시간 (Sub-quadratic time) : 만약 T(n) = o(n²)이면, 서브-이차 시간의 알고리즘이라고 말할 수 있다.
• 다항 시간 (Polynomial time) : 만약 어떤 상수 k에 대해 T(n) = O(n^k)와 같이, 입력 크기에 어떤 다항 표현의 상한을 가지고 수행이 되는 알고리즘이 있다면, 그 알고리즘은 다항 시간을 가진다고 말할 수 있다. 

---

공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘을 실행하는데 필요한 메모리의 양을 설명한다. 즉, 공간 복잡도는 프로그램을 실행하는데 필요한 대략적인 총 추가 공간이라고 말할 수 있다.

 

알고리즘 정렬에 따른 메모리 할당은 아래의 차트와 같이 할당된다.

출처 : Interview kickstart [Time and Space Complexities of Sorting Algorithms Explained]

맨 왼쪽에 worst case라고 쓰여있는 이유는 아무리 최악의 경우라도 저 값을 가진다는 의미이다!

 

서칭을 하다가 복잡도의 최악, 최선, 평균 케이스를 계산하는 표기법을 보았다. 위의 Best, Average, Worst는 아래의 표현법과 연결된다.

빅-오(Big-O) 표기법 : 해당 알고리즘의 복잡도의 상한, 어떤 입력이 주어져도 이 시간 이상은 넘지 않는 다는 뜻이다.

빅-오메가(Big-Omega) 표기법 : 해당 알고리즘의 복잡도의 하한, 어떤 입력이 주어져도 이 시간이 이것보다 낮을 수 없다는 뜻이다.

빅-세타(Big-Theta) 표기법 : 해당 알고리즘의 정확한 복잡도, 위의 두 경우의 가장 적합한 시간의 평균을 알아낸다.

 

보통 시간 복잡도는 일반적으로 빅-오 표기법으로 사용한다. 컴퓨터의 차이에 관계없이 최악의 시나리오를 설명하여 최적으로 필요한 실행 시간 또는 공간을 책정할 수 있기 때문이다!

 

시간 복잡도(알고리즘의 복잡도)를 비교하자면

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) 이다. 아무래도 복잡도가 낮은 정렬을 더 선호하겠지!

---

그러면 몇몇 정렬들을 직접 만들어보자!

 

✨다음 포스팅에서 계속..✨

 

 

출처

https://fintecuriosity-11.tistory.com/186

[알고리즘] 알고리즘이란?

https://namu.wiki/w/%EC%95% 8C% EA% B3% A0% EB% A6% AC% EC% A6%98

알고리즘 - 나무위키

https://www.interviewkickstart.com/learn/time-complexities-of-all-sorting-algorithms

Time and Space Complexities of all Sorting Algorithms

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

시간 복잡도 - 위키백과, 우리 모두의 백과사전