# 알고리즘 이론

3개의 포스트
post-thumbnail

시간 복잡도 (big-O, big-Ω, big-θ)

O (Big-O) 학계에서 big-O는 시간의 상한을 나타낸다. =big-Ω 즉, 위처럼 배열의 모든 값을 출력하는 알고리즘으로 예를 들자면, Ω(N) 뿐만 아니라 Ω(logN), Ω(1)도 마찬가지로 얼마든지 표현이 가능하다. θ (Big-Theta) 위 두 개념에 대해 읽어봤다면, 라는 생각이 들었을지도 모른다. big-O의 경우 그냥 무슨 알고...

2019년 8월 19일
·
0개의 댓글
post-thumbnail

정렬 알고리즘 정리

O(N^2) 정렬 버블정렬(Bubble Sort) 버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다. 오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다. 맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장되기 때문에 (전체 배열의 크기 – 현재...

2019년 8월 19일
·
0개의 댓글
post-thumbnail

그래프 알고리즘 정리

그래프? 정점과 간선들로 이루어진 집합. 즉 트리 역시 그래프에 속한다고 할 수 있다. 그래프를 표현하는 세가지 방법 1. 간선 리스트 말그대로 배열에 간선들을 저장한다. 가장 간단하게 구현되지만 한 정점의 간선에 대한 정보를 얻으려면 모든 간선리스트를 탐색해야 하기 때문에 벨만-포드 알고리즘과 크루스칼 알고리즘 같은 일부 알고리즘이 아니고...

2019년 8월 13일
·
0개의 댓글