Embedded Files
시간 복잡도와 공간 복잡도의 개념
시간 복잡도 : 특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 프로그램 수행 시간을 의미한다 이것은 알고리즘을 시작하고 종료할 때까지 걸리는 시간으로 일반적으로 알고리즘에 포함된 명령어 수행 횟수를 뜻한다.
공간 복잡도 : 특정 알고리즘이 어떤 문제를 해결하는 데 차지하는 공간의 함께 메모리 공간이 커지면서 그 중요도는 떨어졌다. 따라서 최근에는 시간 복잡도를 중심으로 효율적인 알고리즘을 정하기도 한다. 그러나 빅데이터와 같이 데이터 처리 양이 많은 경우에는 공간 복잡도에 따라 메모리 부족 현상이 발생 할 수 있다.
정렬 알고리즘으로 정렬해보고 시간복잡도는
4-1. 선택 정렬 (Selection Sort)
선택 정렬은 최솟값을 찾아서 앞쪽으로 교환하는 방식이드
초기 상태: G W A N G D E O K
(인덱스: 0 1 2 3 4 5 6 7 8)
첫 번째 자리(0번 인덱스)에서 최솟값 찾기
→ A와 G 교환 → A W G N G D E O K두 번째 자리(1번 인덱스)에서 최솟값 찾기
→ D와 W 교환 → A D G N G W E O K세 번째 자리(2번 인덱스)에서 최솟값 찾기
→ E와 G 교환 → A D E N G W G O K네 번째 자리(3번 인덱스)에서 최솟값 찾기
→ G와 N 교환 → A D E G N W G O K다섯 번째 자리(4번 인덱스)에서 최솟값 찾기
→ G와 N 교환 → A D E G G W N O K여섯 번째 자리(5번 인덱스)에서 최솟값 찾기
→ K와 W 교환 → A D E G G K N O W일곱 번째 자리(6번 인덱스)에서 최솟값 찾기
→ N은 이미 최소 → 그대로 둠여덟 번째 자리(7번 인덱스)에서 최솟값 찾기
→ O는 이미 최소 → 그대로 둠마지막 자리(8번 인덱스)는 자동 정렬 완료!
정렬 결과: 👉 A D E G G K N O W
2. 버블 정렬
버블 정렬은 인접한 두 개를 비교하며 Swap하는 방식이다.
초기 상태: G W A N G D E O K
첫 번째 패스:
G vs W → 그대로
W vs A → Swap → G A W N G D E O K
W vs N → Swap → G A N W G D E O K
W vs G → Swap → G A N G W D E O K
W vs D → Swap → G A N G D W E O K
W vs E → Swap → G A N G D E W O K
W vs O → Swap → G A N G D E O W K
W vs K → Swap → G A N G D E O K W
두 번째 패스:
G vs A → Swap → A G N G D E O K W
G vs N → 그대로
N vs G → Swap → A G G N D E O K W
N vs D → Swap → A G G D N E O K W
N vs E → Swap → A G G D E N O K W
N vs O → 그대로
O vs K → Swap → A G G D E N K O W
세 번째 패스:
A vs G → 그대로
G vs G → 그대로
G vs D → Swap → A G D G E N K O W
G vs E → Swap → A G D E G N K O W
G vs N → 그대로
N vs K → Swap → A G D E G K N O W
이 과정을 반복하면...
👉 최종 결과: A D E G G K N O W
3.합병 정렬 알고리즘으로 정렬했을때의 시간복잡도는 O(NlogN)
분할과정
[ G W A N G D E O K ]
→ [ G W A N ] [ G D E O K ]
→ [ G W ] [ A N ] [ G D ] [ E O K ]
→ [ G ] [ W ] [ A ] [ N ] [ G ] [ D ] [ E ] [ O ] [ K ]
정렬하며 병합
→ [ G W ] (정렬) → [ G W ]
→ [ A N ] (정렬) → [ A N ]
→ [ G D ] (정렬) → [ D G ]
→ [ E O K ] (정렬) → [ E K O ]
병합과정
→ [ G W ] + [ A N ] → [ A G N W ]
→ [ D G ] + [ E K O ] → [ D E G K O ]
→ [ A G N W ] + [ D E G K O ] → [ A D E G G K N O W ]
결론:
모든 정렬 알고리즘은 같은 결과 **"A D E G G K N O W"**를 도출함.
**선택 정렬, 버블 정렬은 O(n2)O(n^2)O(n2), 합병 정렬은 O(nlogn)O(n \log n)O(nlogn)**이므로, 데이터가 많아질수록 합병 정렬이 가장 빠름!
순차 탐색의 개념과 시간복잡도
순차 탐색 (Linear Search) – 개념과 시간 복잡도
1. 순차 탐색의 개념
순차 탐색(Linear Search)은 배열이나 리스트에서 원하는 값을 하나씩 차례대로 비교하여 찾는 알고리즘입니다.
즉, 데이터를 처음부터 끝까지 하나하나 확인하면서 일치하는 값을 찾는 방식입니다.
순차 탐색 과정
배열의 첫 번째 원소부터 시작하여 차례대로 각 원소를 확인합니다.
찾고자 하는 값과 동일한 값이 발견되면 탐색을 종료하고, 해당 값을 반환합니다.
만약 배열의 끝까지 확인했음에도 원하는 값을 찾지 못하면, "값이 없다"는 결과를 반환합니다.
2. 순차 탐색의 시간 복잡도
순차 탐색은 배열이나 리스트의 모든 원소를 하나씩 확인해야 하기 때문에, 최악의 경우 배열의 모든 원소를 탐색해야 합니다.
최악의 경우: 배열의 마지막 원소까지 확인할 때 (예를 들어, 찾는 값이 배열의 끝에 있거나 배열에 없을 때)
시간 복잡도: O(N) (N은 배열의 원소 개수)
최선의 경우: 배열의 첫 번째 원소에서 찾는 값을 바로 발견할 때
시간 복잡도: O(1) (상수 시간)
정리
시간 복잡도는 최악의 경우 **O(N)**입니다. (배열에 N개의 원소가 있을 때)
순차 탐색은 배열이나 리스트가 정렬되어 있지 않더라도 사용 가능하며, 데이터가 많지 않은 경우 유용하게 쓰일 수 있습니다.
이진 탐색 (Binary Search) – 개념과 시간 복잡도
1. 이진 탐색의 개념
이진 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 탐색 알고리즘입니다.
배열이 오름차순 또는 내림차순으로 정렬되어 있어야만 사용할 수 있습니다. 이진 탐색은 탐색 범위를 반씩 나누어가며 반복적으로 중간값과 비교하여 원하는 값을 찾습니다.
이진 탐색 동작 과정
중간값 선택:
배열의 중간값을 선택하고, 찾고자 하는 값과 비교합니다.비교 후 이동:
찾고자 하는 값이 중간값보다 작으면 배열의 왼쪽 절반으로 이동합니다.
찾고자 하는 값이 중간값보다 크면 배열의 오른쪽 절반으로 이동합니다.
반복:
탐색 범위가 하나의 원소만 남을 때까지 위의 과정을 반복합니다.결과:
원하는 값을 찾으면 그 값을 반환합니다.
찾지 못하면 없음을 반환합니다.
새로운 중간값 선택:
새로 선택된 범위에서 중간값은 11입니다.
2. 이진 탐색의 시간 복잡도
이진 탐색의 시간 복잡도는 탐색 범위가 절반으로 줄어들기 때문에 매우 효율적입니다.
최악의 경우: 배열에서 값이 있을지 없을지 모르므로, 최대한 중간값을 선택하여 범위를 절반씩 줄여가며 진행합니다.
처음에는 N개의 원소가 있고, 매번 절반씩 범위를 줄여 나가므로, 최대 비교 횟수는 **log₂(N)**번입니다.
따라서 **시간 복잡도는 O(log N)**입니다.
최선의 경우: 중간값을 바로 찾아서 값을 즉시 반환하는 경우로, **O(1)**이 됩니다.
정리
이진 탐색의 시간 복잡도: O(log N)
한 번 비교할 때마다 탐색해야 할 데이터가 절반으로 줄어드므로 빠른 탐색이 가능합니다.
이진 탐색을 사용할 수 있는 조건:
배열이 정렬되어 있어야 합니다.
정렬된 배열에서 원하는 값을 찾을 때 매우 유용하고 효율적인 방법입니다.
Page updated
Google Sites
Report abuse