😑들어가면서😑
알고리즘이 뭔지 어떤 알고리즘이 있는지 공부해보자...📕 알고리즘
알고리즘이란, 어떤 문제를 해결하기 위해 밟아 나가는 연속적인 단계를 말한다.
📒 알고리즘의 요건
- 명확함 : 각 단계가 명료하고 간결하며 모호하지 않다.
- 효율성 : 각 동작이 문제해결에 기여한다.
- 유한함 : 알고리즘이 유한한 단계를 거친 후 종료된다는 뜻이다.
- 정확성 : 입력이 같을 때, 항상 같은 결과를 내야하며, 정확한 답이어야한다.
(몇몇의 알고리즘은 정확성이 덜 필요한 경우가 있다.)
📕 알고리즘의 평가 기준
🤔 알고리즘을 어떻게 분석할 수 있을까...?
📖 시간 복잡도
📒 실행 시간
개발자가 짠 알고리즘을 컴퓨터가 실행하는데 걸리는 시간을 말한다. 실행시간은 사용할 수 있는 자원, 컴퓨터의 성능, 프로그래밍언어,알고리즘 단계,데이터의 크기등에 의해 좌우된다.
📒 알고리즘 단계와 데이터 크기
- 알고리즘 단계 : 알고리즘에 필요한 단계
f(n): 알고리즘에 필요한 단계를 수식으로 표현한다. - 데이터의 크기 :
f(n)의 변수 n
⭐ 중요한 것은 데이터 크기 증가에 따른 알고리즘의 단계의 증가이다.
데이터가 한개인 상황을 생각해보면, 어떤 알고리즘이든 큰 문제가 일어나지 않는다. 그러나 데이터 세트가 클 때는 비효율적인 알고리즘의 효율성이 아주 중요해진다.
빅 O 표기법
n이 커질 때 알고리즘의 시간 또는 공간의 요건이 얼마만큼 증가하는가를 표기하는 방법이다.
T(n)에서 지배적인 부분이 빅 O 표기법에서 도출하는 알고리즘의 규모가 되는 것이다.
효율적인 것 비효율적인 것
상수시간 > 로그시간 > 선형시간 > 선형 로그 시간 > 2차 시간 > 3차 시간 > 지수 시각📒 상수 시간 O(1)
- n의 크기에 관계없이 동일한 단계만 필요한 경우이다.
항상 첫번째 데이터를 출력하는 경우: 하나의 단계만이 필요허다.
📒 로그 시간 O(log n)
- 데이터의 로그애 비례해 알고리즘의 단계가 늘어나는 경우
알고리듬의 탐색범위를 1/2로 줄여나가는 이진 탐색
📒 선형 시간 O(n)
- 데이터의 크기가 커지는 만큼 같은 비율로 단계가 늘어나는 알고리즘이다.
📒 선형 로그 시간 O(n log n)
- 로그 시간 복잡도와 선형 시간 복잡도를 곱한 만큼 커지는 알고리즘이다.
📒 2차 시간 O(n**2)
- n의 제곱에 정비례해서 복잡도가 늘어난다.
- 루프문을 중첩하는 경우에 이럴 수 있다.
- 정렬알고리즘의 상당수가 2차 시간 복잡도를 가진다.
📒 3차 시간 O(n**3)
- n의 세제곱에 정비례해서 복잡도가 늘어난다.
- 루프가 세 번 중첩되어 있는 경우다.
- ⚠️ 가급적 사용을 지양해야하나 피치 못하게 사용할 수 있다.
2차 시간 복잡도와 3차 시간 복잡도 모두 다항 시간 복잡도해 해당한다.
📒 지수 시간 O(c**n)
- 🤮 데이터의 크기만큼 곱해서 복잡도가 늘어난다.
n개의 숫자로 이루어진 비밀번호의 모든 조합을 구할 때 지수시간 복잡도의 알고리즘을 사용할 수 있다.
🤔 만약 자리수가 20자리라면?
👉 영영 구할 수 없을 것이다. 이렇게 가능한 경우의 수를 전부 대입해보는 알고리즘을 무차별 대입 알고리즘이라고 한다.
시간복잡도의 경우 : 최선 vs 최악 vs 평균
데이터의 질에 따라서 알고리즘의 시간복잡도를 계산해볼 수 있다.
😊 일반적으로는 평균의 경우로 시간 복잡도를 계산한다.
🤔 만약 내가 정렬이 안되어 있는 데이터에서 강감찬을 찾는다고 할 때
- 최선 : 강감찬이 맨 앞에 !!
- 최악 : 강감찬이 맨 뒤에
- 평균 : O(n/2)
📖 공간 복잡도
알고리즘의 실행을 완료할 때까지 필요한 자원의 양이다.
고정 공간, 데이터 구조 공간, 임시 공간의 메모리를 얼마나 사용하는지를 나타낸다.
- 고정 공간 : 프로그램 자체가 차지하는 메모리
- 데이터 구조 공간 : 데이터 세트가 차지하는 영역 (n에 따라 달라진다.)
- 임시 공간의 메모리 : 알고리즘에서 중간 처리를 위해 사용하는 메모리이다.
😊 공간복잡도도 빅 O 표기법으로 적용이 가능하다.
📖 복잡도가 중요한 이유
👏 알고리즘의 규모를 줄이기 위해서 규모를 파악해야한다.
같은 문제를 중첩되지 않은 루프로 쓴다면 시간복잡도를 선형 시간으로 줄일 수 있을 것이다.
그런데 중첩된 루프문을 쓴다면 시간 복잡도가 2차 시간으로 늘어나 성능이 저하될 것이다.
이런 알고리즘의 선택은 실제 성능에 영향을 주기 때문에 중요하다.
📌 따라서 시간복잡도를 계산하는 것 또한 중요하다.
만약 데이터의 경우가 최선이라면 2차시간의 알고리즘을 선형 시간의 알고리즘처럼 구현할 수도 있을 것이다...