종류
에 따라, 컴퓨터의 사양
에 따라 변한다.“가상컴퓨터+가상언어+가상코드”
위에서 작업한다.RAM(Random Access Machine)
위에서 동작한다“CPU + Memory + 기본연산”
으로 이루어져있다.A=B
+,-,*,/
>, <, =>, =<, ==, !=
and, or, not
bit-and, or ,not
⇒ 알고리즘의 수행시간은 최악의 입력에 대한 기본 횟수로 정의한다.
# A = [_,_,_,] list size = n
# W.T.C = A의 모든값이 짝수인 경우
def algorithnm1_arrayMax(A,n):
currentMax = A[0]
for i in range(0, n-1):
if currentMax < A[i]:
currentMax = A[i]
return currentMax
# 최종 연산횟수 T(n) = 2n-1
def algorithnm3_sum1(A,n):
sum = 0 # 연산 1회(대입연산)
for i in range(0, n-1): # 연산 n번(반복연산)
if A[i] / 2 == 0: # 연산 2회 (산술연산, 비교연산)
sum += A[i] # 연산 2회 (산술연산, 대입연산)
return sum # n x 4 연산
# 최종 W.T.C 연산횟수 T(n) = 4n+1
def algorithnm3_sum2(A,n):
sum = 0 # 연산 1회(대입연산)
for i in range(0, n-1): # 연산 n번(반복연산)
for j in range(i, n-1): # 연산 n-1번(반복연산)
sum += A[i]*A[j] # 연산 n(n-1)의 2분의1 x 3
return sum
# 최종 W.T.C 연산횟수 T(n) = (3분의2)n제곱 - (3분의2)n + 1
알고리즘의 수행시간 = 최악의 경우의 입력에 대한 기본연산 횟수 =
W.T.C(Worstcase Time Complexity)
algorithnm1(arrayMax) : = 2n-1
algorithnm2(sum1) : = 4n+1
algorithnm3(sum2) : =
1. algorithnm2가 algorithnm1보다 2배 느리다
2. algorithnm3는 $n<\frac{5}{3}$면 algorithnm2보다 빠르다
3. algorithnm3는 모든 n에 대해서 algorithnm1보다 느리다
4. algorithnm3은 $n>\frac{5}{3}$면 항상 algorithnm2보다 느리다.
5. $T_1(n)$ 과 $T_2(n)$는 선형적으로 정비례하게 증가하고 $T_3(n)$은 제곱으로 증가한다. 증가율은 최고차n의 최고차항이 된다.
Big-O의 표기법이란? 함수값을 결정하는 최고차항으로 만 간단하게 표기하는 방법
= 2n-1 ⇒ O(n)
= 4n+1 ⇒ O(n)
= ⇒ O()
Big-O의 다른 예
def incrument_one(a):
return a+1 # 연산 1회(산술연산)
def number_bit(n):
count = 0 # 연산 1회(대입연산)
while n > 0: # 연산 log2의 n회(반복연산)
n = n //2 # 연산 2(산술연산, 대입연산)
count +=1 # 연산 2회(산술연산, 대입연산)
return count
increment_one : = O(1)
number_bit :
= =( → → )