시간복잡도2 [📚누구나 자료구조와 알고리즘] 4. 버블 정렬과 O(N^2) 정렬이란 단어는 알고리즘을 몰라도 이미 익숙한 단어이다. 엑셀에도 여러 값이 있는 자료를 '정렬'하면 해당 값들이 오름차순 또는 내림차순으로 정렬된다. 정렬 알고리즘도 이와 같이 '정렬되지 않은 배열을 오름차순으로 정렬'하는 방법들이다. 컴퓨터 과학분야에서 오랜 기간동안 다양한 정렬 알고리즘들이 연구 & 개발되었다. 버블 정렬 (Bubble sort) 그 중 가장 기본적인 (그리고 상대적으로 비효율적인) 정렬 알고리즘인 버블 정렬은 아래 gif와 같이 진행된다.(출처) 버블정렬은 원소를 순서대로 두 개씩 비교하면서, 왼쪽 값이 오른쪽 값보다 큰 경우 두 값을 서로 교환하고(swap), 그렇지 않으면 그대로 둔다. 그 다음 오른쪽으로 한 칸 이동해서 똑같은 작업을 수행한다. 이렇게 가장 오른쪽 원소까지 이.. 2022. 9. 13. [📚누구나 자료구조와 알고리즘] 3. Big-O Notation : O(N), O(1), O(logN), O(N^2) 빅오 (Big-O) 컴퓨터 과학자들이 알고리즘의 효율성(시간복잡도)을 표기하기 위해 수학적 개념을 차용한 방법이 빅 오 표기법이다. [1] 원소가 N개일 때, 알고리즘에 최대 몇 단계가 필요할까? [2] 원소가 N개일 때, 원소가 늘어남에 따라 알고리즘에 필요한 단계 수가 어떻게 늘어날까? 중요 ! 빅오표기법은 결국 위의 질문에 대한 답을 O()의 괄호 내에 나타내는 것이다. O(N) 선형검색 알고리즘의 경우, 최악의 경우 원소 갯수 만큼의 단계가 필요하다. 예를 들어 100개의 원소 중 찾는 원소가 맨 마지막에 있거나, 없는 경우 100번을 모두 검색해야 하기 때문이다. 고로 선형검색을 위의 1번 질문에 대입해보자면 (= 원소가 N개일 때, 선형 검색에는 최대 몇 단계가 필요할까?) 답은 N 이다. 이.. 2022. 9. 13. 이전 1 다음 반응형
