자바의 특성과 알고리즘 기본 - 1
목차
소개
시작에 앞서 본 글은 boostcourse에서 제공해주는 Rob Edwards 교수님의 “자바로 구현하고 배우는 자료구조” 강좌를 복습하며 정리하는 글임을 밝힙니다.
자바로 구현하고 배우는 자료구조 > 오리엔테이션 : 부스트코스
이번 글에서는 자료구조에 대한 간단한 소개와 함께 복잡성, 그리고 자바에 관한 내용을 다뤄보겠습니다.
자바 특성 및 알고리즘 기본
언어에 대한 이해와는 별개로, 개발자로서 필수적으로 알아야 할 개념 중 자료구조와 알고리즘은 결코 빼놓을 수 없는 것 같습니다.
자료구조는 왜 필요한 걸까요?
강의를 통해 연결 리스트, 스택 & 큐, 해시, 트리, 정렬 에 대해 배우게 될텐데, 이러한 개념들은 어디에 사용되고, 또 어떤 효과를 가져다 줄까요?
비전공자로 첫 개발 입문을 C언어 책으로 했었기에, 비록 그 수준은 얕지만 컴퓨터를 다루는 일에 데이터를 효율적으로 처리하는 것이 중요하다는 사실을 어렴풋이 알고 있습니다.
그리고 자료구조는 많은 양의 데이터를 관리하기 위한 방법으로 사용자의 복잡한 명령어를 효율적으로 처리하기 위해 사용되는 개념이라고 할 수 있습니다.
그렇다면 효율적이라는 것의 기준에 대해서도 살펴볼 필요가 있을 것 같습니다.
복잡도는 알고리즘의 효율을 나타내는 척도인데, 본 강의에서는 시간 복잡도에 대해 소개합니다.
시간 복잡도
시간 복잡도는 서로 다른 알고리즘의 효율성을 비교할 때 사용합니다.
몇 가지 규칙이 있는데, 아래와 같습니다.
-
- input ≥ 0
- 입력값(n)은 항상 0보다 크다.
-
- functions do more work for more input
- 함수는 많은 입력값이 있을 때 더 많은 작업을 하게 된다.
-
- drop all constants
- 시간 복잡도에서는 모든 상수를 삭제한다.
-
- ignore lower order terms
- 낮은 차수의 항들은 무시한다.
-
- ignore the base of logs
- 시간 복잡도 함수가 log 함수를 포함할 경우 밑은 무시한다.
-
- 2n=O(n) => 2n \in O(n)2n∈O(n)
- 등호를 사용하여 표현한다.
예를 들어, 시간 복잡도가 1인 경우는 입력값과 상관 없이 상수 시간이 걸리는 것을 나타내고, 시간복잡도가 n인 경우에는 입력값(n)에 비례하는 선형 시간을 나타냅니다.
그리고 빅 오 표기법을 통해 알고리즘을 다른 알고리즘과 비교해서 표현하는 것이 가능합니다.
(복잡도가 n인 알고리즘에 빅 오 표기법을 적용한 그래프. x축은 복잡도 n, y축은 필요한 일의 양이나 메모리)
다른 알고리즘이 복잡도 n인 알고리즘의 아래에 있다면, 같은 일을 하는 데 시간이 덜 들기 때문에 더 빠른 알고리즘이라 합니다. 반대로, 복잡도 nn 인 알고리즘의 위에 있다면, 더 느린 알고리즘입니다.
빅 오 표기법에서는 이러한 알고리즘 간의 관계를 다음과 같이 표현합니다.
- O (빅 오 복잡도) : 비교 대상인 그래프가 일치 혹은 아래에 있을 때. 비교 대상인 다른 알고리즘과 같거나 더 빠르다.
- θ (세타 복잡도) : 비교 대상인 그래프가 일치할 때. 비교 대상인 다른 알고리즘과 같다.
- Ω (빅 오메가 복잡도) : 비교 대상인 그래프가 일치 혹은 위에 있을 때. 비교 대상인 다른 알고리즘과 같거나 느리다.
- o (리틀 오 복잡도) : 비교 대상인 그래프가 아래에 있을 때. 비교 대상인 다른 알고리즘보다 더 빠르다.
- ω (리틀 오메가 복잡도) : 비교 대상인 그래프가 위에 있을 때. 비교 대상인 다른 알고리즘과 느리다.
다음 강의에서는 자바의 특성에 대해 살펴보도록 하겠습니다.
댓글남기기