이자다의 기록

계산 복잡도와 시간 복잡도: 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한지를 나타낸 정도를 '계산 복잡도'라고 한다. 계산 복잡도는 '시간 복잡도'와 '공간 복잡도'로 나눌 수 있다. 빅 오 표기법: 계산 복잡도를 표현하는 방법에는 여러가지가 있는데, 그 중 '빅 오 표기법'을 주로 사용한다. 이 글에선 시간복잡도와 빅 오 표기법을 공부할 예정이다. 알고리즘이 빠르다, 느리다는 시간으로 표현하지 않는다. 다시말해, 초, 분, 시간으로 표현하지 않는다는 말이다. 왜나하면 같은 알고리즘이라도 하드웨어의 차이로 인해 수행시간이 달라지기 때문이다. 문서 작업용 노트북의 처리속도와 게이밍 컴퓨터의 처리속도가 같을 수는 없다. 따라서 알고리즘의 스피드는 곧 '알고리즘이 완료까지 걸리는 절차의 수..

def sum_mul(n): sum=0 for i in range(1, n+1): sum=sum+(i**2) # 거듭제곱은 ^ 기호가 아니라 ** 기호더라 return sum print(sum_mul(10)) def sum_mul2(n): return n*(n+1)*(2*n+1)//6 print(sum_mul2(10)) 1-1. 1부터 n까지 연속한 숫자의 제곱의 합을 구하는 프로그램을 for문으로 만들기 배운걸 응용하기만 하면 됐고 거듭제곱 기호가 C와는 다르게 ' ^ '가 아니라 ' ** '인 것을 알게 되었다. 1-2. 연습문제 1-1의 시간복잡도는 O(1)인가 O(n)인가? O(n). 입력값n과 계산 횟수(거듭제곱 한 번, 덧셈 한 번)가 정비례하여 증가하기 때문에 O(n)이다. 1-3. 1부터 ..

def sum_n(n): s=0 for i in range (1, n+1): # 1 이상 n+1 미만 s=s+i return s print(sum_n(10)) print(sum_n(100)) def sum_n2(n): return n*(n+1)//2 # /는 소숫점 나오는 나눗셈, //은 정수 나눗셈 print(sum_n2(10)) print(sum_n2(100)) 첫 번째 방법은 흔히 프로그래밍을 처음 입문하는 사람들이 배우는 방법인데 이는 숫자가 1 늘어나면 계산 횟수가 1회 늘어나는 방식이다. 즉 1000을 입력하면 1000번 더해야한다. 0 + 1 + 2 + 3 + 4 + 5 -> 5를 입력하면 5번 더하게 된다. 두 번째 방법은 가우스가 만들었다 알려진 공식을 이용하는 방법이다. 이 공식을 이용..