조금씩 꾸준히 완성을 향해

복잡도(Complexity) 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 => 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘 빅오 표기법(Big-O Notation) 가장 빠르게 증가하는 항만을 고려하는 표기법 (함수의 상한만을 나타냄) ▶ 표현 방법 n이 증가할 때 가장 빨리 증가하는 항(최고차 항)만 남기고 다른 항은 모두 생략 가장 빨리 증가하는 항에 곱해진 상수 역시 생략 남은 항을 O() 안에 넣어 표기 알고리즘 설계 Tip ▶ 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우 C언어를 기준으로 통상 1~3초 가량 시..

Time Complexity 수행시간이란 특정 입력에 대해 수행되는 알고리즘의 기본연산(primitive operation)의 횟수를 말한다. (가상컴퓨터에서 가상언어로 작성된 가상코드를 실행한다고 가정 알고리즘의 수행시간 = 최악의 경우의 입력(worst-case input)에 대한 기본연산의 수행 횟수 입력의 크기 n에 대한 함수 T(n)으로 표기 -> 어떠한 입력에 대해서도 T(n) 시간 이내에 종료됨을 보장 ▶ example #input : n개의 정수가 담긴 배열 A #output : A의 수 중에서 최대값 def func(A, n): max = 0 # 1번(할당) for i in A: if i > max: # n-1번(크기를 확인하는 최악의 경우) max = i # n-1번(할당을 하는 최악의..