복잡도

시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 '시간' 분석
공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 '메모리 사용량' 분석
복잡도가 낮을 수록 좋은 알고리즘

표기방법

빅오표기법:차수가 가장 큰 항만 남긴다.

    O(1)
    O(logN)
    O(N)    :N개의 데이터의 합을 계산하는 프로그램
    O(NlogN)
    O(N^2)  :2중 반복문

알고리즘 설계Tip

    일반적인 CPU기반 연산 횟수 5억 넘어가면
            C언어:1-3sec
            Python:5-15sec(PyPy)
    코딩테스트 문제에서 시간제한은 1-5초가량임
    (1초에 2천만번 정도라고 생각하고 풀어야)

요구사항따라 적절한 알고리즘 설계Tip

시간제한 1초인 문제 만났을 때, 일반적 기준

N의 범위가 500 >>O(N^3)
N의 범위가 2,000 >>O(N^2)
N의 범위가 100,000 >>O(NlogN)
N의 범위가 10,000,000 >>O(N)

알고리즘 문제 해결 과정

1.지문읽기 및 컴퓨터적 사고
2.요구사항(복잡도) 분석
3.문제 해결을 위한 아이디어 찾기
4.소스코드 설계 및 코딩

수행시간 측정 방법

import time
start_time = time() #측정 시작
thtmzhem
end_time = time.time() #측정 종료
print("time:",end_time - start_time) #수행 시간 출력