알고리즘이란?
- 어떠한 문제를 해결하기 위한 여러 동작들의 모임
알고리즘의 목표는 주어진 입력 데이터를 효율적으로 처리하여 원하는 출력을 생성하는 것이다.
즉,
입력과출력이 정해져 있고 효율적인 처리결과를 통해서 출력을 도출해내는 것
알고리즘 조건
-
입력 : 외부에서 제공되는 자료가 0개 이상 존재해야 한다.
-
출력 : 적어도 2개 이상의 서로 다른 결과를 내어야 한다.
-
명확성 : 수행과정은 무엇을 하기위한 것인지 명확하게 정의되어야 한다.
-
유한성 : 알고리즘의 명령어대로 수행했을 때 처리된 후 종료되어야 한다.
-
효율성 : 모든 과정은 명백하게 실행가능한 것이어야 하며,
시간적 공간적 효율성을 가져야한다.
시간복잡도, 공간복잡도
빅오 표기법 (Big - O notation)
- 빅오 표기법은 알고리즘의 효율성을 표기해주는 표기법이다.
알고리즘 최악의 실행 시간의 척도가장 많이 사용하는 표기법이다. 최소한 보장되는 성능을 표기하기 때문에 가장 일반적으로 사용한다.
코드의 실행 시간을 측정할때 언어의 타이밍 함수 System.currentTimeMilis() 를 쓰면 되잖아?
기기 사양이나 실행 시점에 따라 다르게 측정된다. 작은 차이를 정확히 예측하기 어렵다.
대신에, 컴퓨터가 처리하는 연산의 개수를 센다. 어떤 컴퓨터든 연산의 개수는 변하지 않는다.
특정 하드웨어나 소프트웨어 환경에 의존하지 않고 일반적인 방식으로 표현할 수 있게 된다.
빅-오메가 표기법 Big-Ω notation
빅-오메가라고 읽으며 최선의 경우의 성능을 나타낸다. (점근적 하한선)
해당 알고리즘이 아무리 빨라도 기존 비교하는 함수와 같거나 혹은 좋지 않다는 뜻
예시로 Ω(n)은 알고리즘이 최소한 입력 크기(n)에 비례하는 시간이 걸린다는 것을 의미한다.
빅-오 표기법 Big O Notation
빅-오라고 부르며 최악의 경우의 성능을 의미한다. (점근적 상한선)
해당 알고리즘이 아무리 나빠도 이보다 나쁘지 않을 것을 보장한다. (기존 비교하는 함수와 같거나 혹은 좋다.)
최악의 경우를 상정하고 대비할 수 있다. 시스템 설계시 예상치 못한 상황에 대비할 수 있다.
O(1), O(n^2), O(log n) 와 같이 표기한다.
빅-세타 표기법 Big Θ-notation
빅-세타라고 부르며 평균적인 경우의 성능을 나타낸다. (점근적 상한과 하한의 교집합)
빅오와 오메가 표기법의 상한과 하한을 동시에 제공한다.
해당 알고리즘이 아무리 나쁘거나 좋더라도 기존의 비교하는 함수의 범위 안에 존재한다는 뜻입니다.
