전체태그 보기

#알고리즘 이론 (3개의 포스트)

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

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

2019년 8월 19일0개의 댓글
O (Big-O) 학계에서 big-O는 시간의 상한을 나타낸다. big-O (여기서 "학계에서"라는 말을 꼭 짚고 넘어가자, 현업에선 아니라는 뜻이다) 예를들어 배열의 모든 값을 출력하는 알고리즘의 시간복잡도를 O(N)으로 표현할 수 있지만 이를 O(N^2) 이나 O(N!)와 같이 표현해도 문제될 표현은 아니다. 즉, 해당 알고리즘이 big-O로 표...
정렬 알고리즘 정리
wan088

정렬 알고리즘 정리

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

그래프 알고리즘 정리

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