#의사코드 #시간복잡도

의사코드(pseudocode)

• 프로그래밍 언어를 작성하기 전에 우리가 쓰는 언어를 이용해서 작동하는 논리를 먼저 작성해 보는것

장점

1. 시간 단축

• 문제가 복잡하거나 코드 양이 길어진다면 시간이 지나서 로직이 기억나지 않을 수 있다 그렇기 때문에 먼저 작성해둔 수도코드를 보면서 시간을 단축한다

1. 디버깅 용이

• 오류가 났을때 개발 언어로만된 코드를 본다면 어디가 오류인지 알 수 없는 경우가 많다

1. 소통

• 프로그래밍 언어에 익숙하지 않은 사람도 우리가 쓰는 언어로 작성된 수도코드를 보면 이해하기 쉽고 소통할 수 있다

구체적으로 써야하는 이유

• 컴퓨터는 우리가 쓰는 언어를 알지 못하고 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
• 가장 느린 시간 복잡도
• 재귀로 구현한 피보나치 수열이 가장 대표적이다