시간복잡도 (11) 썸네일형 리스트형 [알고리즘] 정렬의 최적성 정렬의 최적성 앞에서 우리는 연속한 두 원소를 비교하는 방식으로 정렬하면, O(n2) 보다 좋은 시간 복잡도를 얻을 수 없다는 것을 보였다. 그 다음에 배운 정렬 방식인 퀵정렬, 병합정렬, 힙정렬 에서는 멀리 떨어진 두 원소를 비교하여 교환함으로써 이보다 빠른 시간 복잡도인 O(n log n) 시간을 얻을 수 있었다. 그렇다면 이제 우리가 다시 비슷한 질문을 해보자. O(n log n)보다 더 빠르게 정렬을 수행할 수 있겠는가? 정리. 두 원소를 비교하여 교환하는 방식으로는 O(n log n)보다 더 빠르게 정렬을 수행할 수 없다. 증명. 의사 결정 트리(decision tree)는 어떤 문제에 대해서 판단을 내리는 과정을 트리로 표현한 것이다. 루트는 문제를 풀기 위해서 처음 시작하는 지점이다. 루트를.. [알고리즘] 비교 기반 정렬 문제 정렬 문제→ 여러 방법이 존재하며, 방법마다 특징이 다름 → 시간복잡도, 최적성에 대해 증명이 쉬움 → n개의 서로 다른 수가 주어질 떄, 이들을 이동하여 점점 커지게(오름차순) 또는 점점 작아지게(내림차순)으로 만드는 문제 가정 : 정렬한 데이터가 담긴 배열의 각 원소를 O(1)시간에 접근 가능하다. (= 데이터가 메인 메모리에 저장되어 있다.) 버블 정렬 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해가면서, 큰 수가 오른쪽으로 가도록 교환함. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복 정확성 : 자명함 시간 복잡도 : 처음 가장 큰 원소를 구할 때 n-1번 비교, 두 번째 큰 원소를 구할 때 n-2번 비교 (n-1) + (n-2) + … + 1 =.. [알고리즘] 알고리즘 개요 및 정의 알고리즘의 정의 : 어떤 입력에도 정확한 출력을 유한한 시간 안에 내는 프로그램 어떤 입력 : 문제의 난이도나, 입력의 크기에 상관없이 문제를 풀 수 있다. 정확한 출력 : 문제가 요구하는 조건을 만족한다. 정답이 요구하는 조건이 무엇인지 명시할 수 있다. 유한한 시간 : 무한루프에 빠지지 않고 납득할 수 있는 시간에 종료한다. ex) 100명의 학생들의 시험 점수 중 최댓값을 구하시오. 수학적 귀납법→ 정확성 : 자명하다. → 시간 : n명의 점수를 읽으면, n-1번 비교. → max(지금까지의 최댓값, i+1번째 학생의 점수) ex) 100명의 학생들의 시험 점수 중 최빈값을 구하시오. ex) 입력 : U={1,2, … , n} 중에서 특정한 수 하나만 빼고 무작위의 순서로 n-1개의 숫자가 한번에 .. 이전 1 2 다음
