시간복잡도

PS/알고리즘

정렬-2

2022.10.01

더 빠르게 정렬할 수는 없을까? 기존의 정렬의 시간 복잡도는 O(n^2) 걸리지만 오늘 배울 합병 정렬과 퀵 정렬은 시간 복잡도가 O(n log n)이 걸리게 된다. 두 정렬은 모두 재귀를 사용하게 된다. 재귀 함수 디자인의 과정 1. 작성하려는 함수의 역할을 말로 명확하게 정의한다. 2. 함수가 기저 조건에서 제대로 동작하게 작성한다. 3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다. 4. 함수를 완성한 후, 기저 조건으로 수렴함을 보인다. 합병 정렬 배열을 절반으로 나누어 각각을 정렬한 후, 합친다. T(n) = n개의 숫자를 합병 정렬할 때의 시간 복잡도 1. 왼쪽 합병 정렬 = T(n/2) 2. 오른쪽 합병 정렬. = T(n/2) 3. 합친다. = O(n) 점화식 = T(n) =2*T(n/..

PS/알고리즘

시간복잡도(기본)

2022.09.30

문제를 효율적으로 해결하는 것은 무엇일까? 똑같은 문제를 해결해도 빠르게 해결하는 것이 중요하다. 같은 입력을 제공했을 때, 어느 프로그램이 더 빠른가? 내 프로그램은 얼마나 빠를까? 라는 의문을 가지고 나오게 된 것이 시간 복잡도이다. 프로그램이 대략적으로 몇 개의 명령을 수행하는가? public class Main { public static void main(String[] args) { int a =1, b= 5; int sum = a+b; System.out.println(sum); } } 위와 같은 코드는 a, b를 선언하고 sum 에다 a+b 값을 넣어주고 출력해주는 코드이다. 위는 대략 3번이 실행되는 데 이것은 O(3)이라고 한다. O는 Big-O를 나타내고 읽을 때는 빅-오 또는 오더라..

정렬-2

시간복잡도(기본)

티스토리툴바