🚩 들어가며...
이 글은, 누구나 자료구조와 알고리즘 [개정2판] 을 보고, 이미 노션에 정리했지만,
1. 자신을 위해 핵심만 골라 다시 정리해보는 글이자,
2. 시간이 부족한 비전공 개발자분들이 BigO에 대한 개념을 얕지만 핵심만 알아가기를 바라며 정리하는 글 입니다.
중요 질문과 답변 위주로 정리하는 형식으로 글을 작성해 보겠습니다.
[책 3-6장의 목차]
3장. 빅 오 표기법
4장. 빅 오로 코드 속도 올리기
5장. 빅 오를 사용하거나 사용하지 않는 코드 최적화
6장. 긍정적인 시나리오 최적화
💥 [참고사항] 빅 오의 수학적 설명 💥
전통적인 대학교육에서 알고리즘을 배우면 수학적 관점에서 빅 오를 소개합니다.
빅 오는 원래 수학 개념이므로 수학 용어로 설명되곤 합니다.
이 책은 수학 지식이 많지 않아도 이러한 개념을 이해할 수 있도록 집필되어있고, 책의 관점에서 정리하는 글입니다.
[목차]
✅빅 오의 필요성
✅ 빅 오 표기법이란?
1. O(N)
2. 빅 오의 본질
3. O(logN)의 해석
4. 빅 오를 사용하는 이유는?
5. 빅 오의 규칙들
6. 평균적인 경우
❓ Big O [빅 오]의 필요성 ❓
✅ 단순히 어떤 알고리즘을 "22단계의 알고리즘", "400단계의 알고리즘" 이라 표시할 수는 없다.
알고리즘에 필요한 단계 수를 하나의 수로 못 박을 수 없기 때문이다.
✅선형 검색을 예로, 선형 검색에는 배열의 원소 수만큼의 단계가 필요하므로 배열에 따라 필요한 단계수가 다르다.
원소가 22개인 배열은 22단계의 선형 검색이 필요하다.
원소가 400개인 배열은 선형 검색에도 400단계가 필요하다.
🟥 선형 검색의 효율성을 정량화하는 보다 효과적인 방법은
배열에 N개의 원소가 있을 떄 선형 검색에 N단계가 필요하다고 표현하는 것이다.
😬 하지만 이 방법은 다소 장황하다... 😬
🍀 Big O (빅 오) 표기법이란?
컴퓨터 과학자는 서로 시간 복잡도를 쉽게 소통할 목적으로
자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해
수학적 개념을 차용했다.
이러한 개념을 형식화한 표현을 빅 오 표기법이라 부른다.
위 표기가 뜻하는 바는 무엇일까?
1️⃣ O(N)
이 표기는 "핵심 질문"에 대한 답을 나타낸다.
여기서 핵시 질문이란?
🍀 "데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?" 🍀
핵심 질문에 대한 답은 빅 오 표현의 괄호 안에 들어 있다.
O(N)은 알고리즘에 N단계가 필요하다는 핵심 질문에 대한 답을 나타낸다.
2️⃣ 빅 오의 본질
🎯 빅 오의 본질이란?
1. 데이터가 늘어날 떄 알고리즘의 성능이 어떻게 바뀌는지를 뜻한다.
✅빅 오는 단순히 알고리즘에 필요한 단계 수만 알려주지 않는다.
✅데이터가 늘어날 때 단계 수가 어떻게 증가하는지 설명한다.
2.별도로 명시하지 않는 한 빅 오 표기법은 일반적으로 최악의 시나리오를 의미한다.
✅ 이는 ‘비관적인’ 접근이 유용한 도구일 수 있기 때문이다.
최악의 시나리오에서 알고리즘이 얼마나 비효율적인지 정확히 알면,
최악을 대비함과 동시에 알고리즘의 선택에 중요한 영향을 미칠 수 있다.
3️⃣ O(logN) 해석
컴퓨터 과학에서 O(logN)은 사실 O(log2N)을 줄여 부르는 말이다.
(단지 편의를 위해 다음 첨자 2를 생략했을 뿐이다.)
1. O(logN)은 데이터 원소가 N개 있을 때 알고리즘에 log2(N)단계까 걸린다는 의미다.
2. 원소가 8개이면 log2(8)=3이므로 이 알고리즘은 3단계가 걸린다.
바꿔말해, 원소 8개를 절반으로 계속해서 나누면 원소가 하나 남을 때까지 3단계가 걸릴 것이다.
🟥 결론
O(logN)은 원소가 하나가 될 때까지 데이터 원소를 계속해서 반으로 줄이는 만큼의 단계수가 걸린다는 뜻이다.
4️⃣ 빅 오를 사용하는 이유는 무엇일까?
1. 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 기회가 생긴다.👀
2. “ 이 알고리즘이 일반적으로 쓰이는 알고리즘만큼 빠른가 혹은 느린가?” 라고 자문해 볼 수 있다.
5️⃣ 빅 오의 규칙들 📢
🚩 규칙1. 빅 오 표기법은 상수를 무시한다.
🚩 규칙2. 빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.
🚩 규칙3. 다양한 차수가 한데 섞여 있을 때 빅 오 표기법은 가장 높은 차수의 N만 고려한다.
🚩 규칙1. 빅 오 표기법은 상수를 무시한다.
[예시]
N/2 단계가 필요한 알고리즘 👉 O(N) 으로 표현
N2 +10 단계 필요한 알고리즘 👉 O(N2) 으로 표현
2N단계가 필요한 알고리즘 👉 O(N) 으로 표현
O(N)보다 100배 느린 O(100N) 👉 O(N) 으로 표현
🚩 규칙2. 빅 오 표기법은 일반적인 카테고리의 알고리즘 속도만 고려한다.
[예시]
실제 건물에 비유해서 논해보면, 건물의 종류는 매우 다양하다.
단층 단독주택, 2층 단독주택, 3층 단독주택이 있다.
층수가 다양한 고층 아파트도 있다.
하나는 단독 주택이고 하나는 고층 건물인 두 건물을 비교할때 굳이 각각이 몇 층인지 언급할 이유가 없다.
두 건물의 크기와 기능이 현저히 달라서 "이 건물은 2층짜리 지빙고, 저 건물은 100층짜리 고층 건물입니다." 라고 말할 필요가 없는 것이다.
일반적인 카테고리로만 분류해도 현저한 차이를 나타내기 충분하다.
✅ 알고리즘 효율성도 마찬가지다.
가령 O(N) 알고리즘과 O(N2) 알고리즘을 비교할 떄 두 효율성간 차이가 너무 커서,
O(N)이 실제로 O(2N)이든 O(N/2) 이든 심지어 O(100N)이든 별로 중요하지 않다.
그래서 O(N)과 O(100N)은 같은 카테고리로 분류하고, O(N)과 O(N2)은 별개의 카테고리로 분류한다.
🟥 데이터가 늘어날 떄 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하다.
아래 그래프를 보면 N에 여러 상수를 곱해도 O(N2)이 느리다. [아래 그래프 참고]
✅ 결론
따라서 빅 오 에서 서로 다른 카테고리에 속하는 두 효율성을 비교할 때 일반적인 카테고리로 분류하는 것으로 충분하다.
🚩 규칙3. 다양한 차수가 한데 섞여 있을 때 빅 오 표기법은 가장 높은 차수의 N만 고려한다.
[예시]
N4 + N3 + N2 + N 단계가 걸리는 알고리즘이 있을 때 N4만 중요하게 여기며 단순하게 O(N4)이라고 부른다.
왜 그럴까?
아래 표를 확인해보자.
N이 증가할수록 어떤 N차수보다 N4의 비중이 훨씬 커져서 작은 차수는 미미해 보인다.
N4 + N3 + N2 + N을 더하면 총 101,010,100이다.
하지만, 내림차순하면 100,000,000이 되어 낮은 차수의 N을 무한 것과 같다.
| N | N2 | N3 | N4 |
| 2 | 4 | 8 | 16 |
| 5 | 25 | 125 | 625 |
| 10 | 100 | 1,000 | 10,000 |
| 100 | 10,000 | 1,000,000 | 100,000,000 |
6️⃣ 평균적인 경우
정의에 따르면 가장 자주 일어나는 경우는 평균 시나리오다.
따라서 평균 시나리오도 중요하게 고려해야 한다.
최선의 그리고 최악의 시나리오는 상대적으로 드물게 발생한다. 실제로는 대부분 평균 시나리오가 일어난다.
🟥 최선의, 평균, 최악의 시나리오를 구분하는 능력은 기존 알고리즘을 최적화해서 훨씬 빠르게 만드는 것만큼이나 사용자 요구에 맞는 최적의 알고리즘을 고르는 핵심 기술이다.
최악의 경우를 대비하는 것도 좋지만, 대부분은 평균적인 경우가 일어난다는 점을 명심하자.
✅ 알아두기
| O(1) | "가장 빠른" 알고리즘 유형으로 분류한다. 상수 시간(constant time)을 갖는 알고리즘이라고도 표현한다. |
| 로가리즘 ( logarithm ) |
🟥 로그는 로가리즘(logarithm)의 줄임말이다. 로가리즘은 지수(exponent)와 역(inverse)의 관계다. 예시) 2^3 = 2 x 2 x 2 와 동치로서 값이 8이다. log2(8)은 2^3의 역(converse)이다. 즉 2를 몇 번 곱해야 8을 얻을수 있는지를 뜻한다. 🙄 더 쉬운 설명 🙄 log2(8)을 다른 방식으로 설명하면 다음과 같다. 1이 될 떄까지 8을 2로 계속해서 나눌 떄 등식에 얼마나 많은 2가 등장할까? 8 / 2 / 2 / 2 = 1 다시말해 1이 나올 때까지 8을 2로 몇번 나눠야할까? 위 예제에서는 '3번' 이다. 이제 로가리즘이 무엇인지 이해했을테니 O(logN)의 의미를 더 명확히 알 수 있다. |
| O(N x M) [p150] |
N과 M이 같으면 O(N2)과 동등하다. 갖지 않으면 더 작은 수를 임의로 M에 할당함으로써 O(N)이 된다. 따라서 어떤 의미에서는 O(N x M)을 O(N)과 O(N2) 사이 정도로 이해할 수 있다. ✅이것이 (책에서 설명하기를) 최선이라고 한다. |
🎯마무리와 생각정리
23년 12월 31일, 23년의 마지막날 빅 오에 대해 정리를 하겠다는 결심을 하고 실행했고,
다행히 글은 잘 마무리 된 것 같다.😀
위에서 적은것과 같이 이미 노션에 한 번 정리한 글이지만, 누군가에게 도움이되었으면 좋겠다는 마음으로 계속 반복해서 읽어보며 재정리를 마무리했다.
책에서 빅 오를 처음 봤을떄, 빅 오에 관해서 수학적 관점에서 완벽하게 알아야 하는 것일까?
라는 생각이 먼저 들긴했다.😱
하지만, 사실상 빅 오(BigO)라는 개념이 나온 배경을 대략적으로 살펴보면,
글 빅오 표기법이란? 에서 설명했듯이
"컴퓨터 과학자는 서로 시간 복잡도를 쉽게 소통할 목적으로 자료 구조와 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기 위해 수학적 개념을 차용했다."
라고 한다.
🟥결국에 빅오(BigO)라는 개념은
개발자에게(나에게) 있어서 더 효율적이고 다른 코드와 비교하기 위해서 사용되는 개념일 뿐이라고 생각이 들었다. (나중에 생각이 바뀔수도 있겠지만 지금은 그렇다.)
따라서 이 글을 읽고 앞으로 코드를 분석하고자하는 사람들에게 해주고 싶은 말은 하나다.
"데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요할까?"
이 핵심질문을 기억하고 본인의 코드에 적용하자.
쓰이지 않는 개념은 잊혀지게 되어있다.
<referense>
1. 누구나 자료구조와 알고리즘 개정2판
'자료구조 & 알고리즘 > 자료구조[data structure]' 카테고리의 다른 글
| [자료구조1편] 자료구조가 중요한 까닭? - [누구나 자료구조와 알고리즘 개정2판 1-2장 요약] (2) | 2023.12.28 |
|---|
댓글