개발새발
#의사코드 #시간복잡도 본문
의사코드(pseudocode)
- 프로그래밍 언어를 작성하기 전에 우리가 쓰는 언어를 이용해서 작동하는 논리를 먼저 작성해 보는것
장점
- 시간 단축
- 문제가 복잡하거나 코드 양이 길어진다면 시간이 지나서 로직이 기억나지 않을 수 있다 그렇기 때문에 먼저 작성해둔 수도코드를 보면서 시간을 단축한다
- 디버깅 용이
- 오류가 났을때 개발 언어로만된 코드를 본다면 어디가 오류인지 알 수 없는 경우가 많다
- 소통
- 프로그래밍 언어에 익숙하지 않은 사람도 우리가 쓰는 언어로 작성된 수도코드를 보면 이해하기 쉽고 소통할 수 있다
구체적으로 써야하는 이유
- 컴퓨터는 우리가 쓰는 언어를 알지 못하고 0,1로만 이루어지기 때문에 자세하게 로직을 적어주지 않으면 컴퓨터에게 명령 할 수 없다
시간복잡도
- 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가
Big-O
- 최악의 경우르 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다
O(1)
- Constant complexity (상수시간)
- 입력값이 증가하더라도 시간이 늘어나지 않는다
- 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다
- 예) for,while문 등을 돌지 않고 바로 인덱스 번호를 찾아 값을 출력한다고 이해함
O(n)
- linear complexity(선형시간)
- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가
- 입력값이 1일때 1초, 입력값이 100배로 증가하면 100초
- 예) 선형탐색처럼 앞에서부터 쭉 가니까 입력값에 따라 시간도 같이 증가한다고 이해
O(log n)
- logarithmic complexity
- O(1)다음으로 빠른 시간 복잡도
- 이진탐색을 할 경우
- 입력값이 크더라도 그 숫자를 찾기위해 절반씩 제거하면서 하기 때문에
O(n2)
- quadratic complexity
- 입력값이 증가함에 따락 시간이 n의 제곱수의 비율로 증가
- 입력값이 1일 경우 1초가 걸리던게 5를 주니까 25초가 걸리면 O(n2)라고 표기
O(2n)
- exponential complexity
- 가장 느린 시간 복잡도
- 재귀로 구현한 피보나치 수열이 가장 대표적이다
'알고리즘' 카테고리의 다른 글
#탐욕알고리즘 #짐나르기 #편의점알바 #자리 옮기기# 금고털기 (0) | 2022.08.03 |
---|---|
탐욕 알고리즘(Greedy) (0) | 2022.08.03 |
#Tree #Graph # BST (0) | 2022.08.03 |
# 스택 #큐 (0) | 2022.08.03 |
Comments