삼성역에서 택시를 타고 강남역으로 향했는데 30분 걸렸다. 구글에서 알려주는 최단경로로 갔더라면 15분내에 도착할 것이다. 레스토랑을 예약해서 가는 경우라던지 친구와 약속시간을 잡은경우 우리에게는 시간은 항상 소중하다. 그래서 우리는 시간을 효율적으로 사용하기위한 노력을 의식적으로 하고 있다.
따라서 알고리즘이란
여기서 알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다. 알고리즘의 실행시간을 두 부분으로 나누면
점근적 표기법은 다음 세가지가 있는데 시간복잡도를 나타내는데 사용된다.
평균인 세타 표기를 하면 가장 정확하고 좋겠지만 평가하기가 까다롭다. 빅오 표기법은 불필요한 연산을 제거하여 알고리즘분석을 쉽게 할 목적으로 사용된다. Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있는데
http://bigocheatsheet.com/ 시간복잡도시간복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다. 시간복잡도에서 중요하게 보는것은 가장큰 영향을 미치는 n의 단위이다.
시간복잡도의 문제해결 단계를 나열 하면 아래와같다.
아래표는 실행시간이 빠른순으로 입력 N값에 따른 서로 다른 알고리즘의 시간복잡도이다.
O(1) : 상수아래 예제 처럼 입력에 관계없이 복잡도는 동일하게 유지된다.
O(N) : 선형입력이 증가하면 처리 시간또는 메모리 사용이 선형적으로 증가한다.
O(N^2) : Square반복문이 두번 있는 케이스
O(log n) O(n log n)주로 입력 크기에 따라 처리 시간이 증가하는 정렬알고리즘에서 많이 사용된다.
시간복잡도를 구하는 요령각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.
정렬 알고리즘 비교
Codeit Logo 로그인 좋은 알고리즘이란?알고리즘 평가법유용한 파이썬 기능 정리 n log n 의 예시를 들어주실 수 있나요?? 2019년 8월 19일 4,309 조회 답변 1 익명 LV 17 익명 LV 17 질문 지켜보기를 시작하면 질문에 답변, 댓글이 달릴 때 알림을 받을 수 있어요. 댓글 0개 0 김석희 2019년 8월 20일 LV 17
댓글 2개 2 2019년 8월 20일 아하 생각했던 것 맞네요.. 길이가 5라면, 나누는데 log 2 5 , 합치는데 5번이라서 5 log 2(5)가 되는거죠? 2019년 8월 23일 네 맞아요! 질문 지켜보기 질문 지켜보기를 시작하면 질문에 답변, 댓글이 달릴 때 알림을 받을 수 있어요. |