무냐의 개발일지
[OSSU] <MITx 6.00.1x_Intro CS> Week6/ Algorithmic Complexity (Time) 본문
| Time efficiency , Complexity
- a program can be implemented in many different ways
- you can solve a problem using only a handful of different algorithms
worst case일 때를 기준으로 time efficiency를 재도록 한다
Input size가 커질수록 programming efficiency가 달라지겠지
- do not need to be precise: “order of” not “exact” growth
| Types of Orders of Growth
보통 nlogn , linear에 속하는 경우가 많다
Explanation:
In the worst case scenario, x is not present in L. Thus we go through the for loop n times. This means we execute assignment of e to each element of L (this takes place in the line for e in L) to enter the for loop, and also execute the check
(루프를 n번 돌고, 비교도 n번 하니까 2*n )
if e == x:
once each for every element. So this is 2*n steps. Finally at the end of the for loop, we execute the return statement one time.
💡 알아둘 점
기본연산(primitive/atomic operation): 단위 시간에 수행할 수 있는 연산으로 정의
a. 복사연산:A=B(B레지스터의값을A레지스터에복사또는 B 레지스터의 값을 A 레지스터에 복사)
b. 산술연산:+,-,*,/(나머지%연산은허용안되나, 본 강의에서는 포함한다) - 레지스터에 복사된 값에 대해 기본연산을 수행
c. 비교연산: >, >=, <. <=, ==, !=
d. 논리연산: AND, OR, NOT
e. 비트연산: bit-AND, bit-OR, bit-NOT,bit-XOR, <<, >>
따라서, L의 n에에 대해 각 루프를 돌면서 & 비교연산을 하는 거니까 2*n번이고
마지막에 return boolean은 복사연산이니까 +1 이 든다.
👩💻 연산 횟수 세기
def program3(L):
totalSum = 0
highestFound = None
for x in L:
totalSum += x
for x in L:
if highestFound == None:
highestFound = x
elif x > highestFound:
highestFound = x
return (totalSum, highestFound)
코드
✍️ 해설
totalSum=0
highestFound=None
return (
--> 이거 세개는 상수시간 : 3
for x in L: (n번 반복)
totalSum += x (2*n번 반복)
--> 3*n
for x in L:
if highestFound == None: (2*n)
highestFound = x
elif x > highestFound: (2*n)
highestFound = x
--> worstcase이려면 계속 highest가 안 찾아져서, elif로 넘어가야함.
(In the worst case scenario, L is a list with its elements sorted in increasing order (eg, [1, 3, 5, 7, ...]). )
--> 4*n 인데, 마지막 n번째 숫자는 if문을 충족할거잖아. 그러면 그 충족하는 애는 1, 1, 1 - 3번 하고 끝나겠지.
--> 4(n-1) + 3 번 하고 끝나는거임
그래서 결국 다 합치면, 3 + 3*n + 4(n-1) +3 = 7*n + 2
지쟈스 ....
| Big -Oh Notation
상수는 제거하고, n의 계수도 제거하고, 그냥 O(n)으로 표기한다
👩💻 문제
#1
def program1(L):
multiples = []
for x in L:
for y in L:
multiples.append(x*y)
return multiples
✍️ 해설
앞뒤 assignment = 2번
for x : assignment = n번
for y: assignment = n x n(3) = 3n^2 (각각의 x마다 각각의 y에 대하여 연산을 해주는거니까)
--> 3*n^2 + n + 2
👩💻 문제
#2
def program2(L):
squares = []
for x in L:
for y in L:
if x == y:
squares.append(x*y)
return squares
✍️ 해설
앞뒤 배정 = 2
for x : n
for y : n(1+1+1+1) = 4n^2 (y에 배정하는 거, if문, append, 곱셈)
--> 4*n^2 + n + 2
👩💻 문제
#3
def program3(L1, L2):
intersection = []
for elt in L1:
if elt in L2:
intersection.append(elt)
return intersection
✍️ 해설
In the worst case scenario, every element of L1 is the same as the very last element of L2.
In this case we go through the loop for elt in L1 n times.
Every time through this loop, we perform one assigment of a value to the variable elt, then we execute the check if elt in L2.
최악의 상황은, elt가 항상 L2에도 있고, 심지어 맨 뒤쪽에 있는 상황이다.
그러면, 모든 elt에 대해서 (n)
if elt in L2 : search를 하는것과 똑같아서, n번을 search해야한다고 가정한다. 그 안에서 elt에 assignment, append (2번)이 있으니
결국 (n+2)
--> 결국 for문 안에서 n*(n+2) 가 이뤄지게 된다
답 : n^2 + 2*n + 2
그리고 이 모든 3개의 경우에 complexity는 O(n^2)이 되겠다.
| Complexity Classes
CONSTANT COMPLEXITY
- complexity independent of inputs
- very few interesting algorithms in this class, but can often have pieces that fit this class
- can have loops or recursive calls, but number of iterations or calls independent of size of input
LOGARITHMIC COMPLEXITY (문제를 반으로 잘라서 루프 도는 경우)
- 매우 효율적 ! complexity grows as log of size of one of its inputs
- example: (보통 while 루프)
◦ bisection search
◦ binary search of a list
def intToStr(i):
digits = '0123456789' if i == 0:
return '0'
result = ''
while i > 0:
result = digits[i%10] + result
i = i//10
return result
LINEAR COMPLEXITY (팩토리얼같은 재귀함수 등)
- searching a list in sequence to see if an element is present
- add characters of a string, assumed to be composed of decimal digits
def addDigits(s):
val = 0
for c in s:
val += int(c)
return val- iterative and recursive factorial implementations are the same order of growth
POLYNOMIAL COMPLEXITY (recursive ex. Nested Loops)
- most common polynomial algorithms are quadratic, i.e., complexity grows with square of size of input
- commonly occurs when we have nested loops or recursive function calls
def isSubset(L1, L2):
for e1 in L1:
matched = False
for e2 in L2:
if e1 == e2:
matched = True
break
if not matched:
return False
return Truenest loop는 n^2 이런 식의 polynomial
EXPONENTIAL COMPLEXITY (가장 expensive하고, 복잡하고 오래걸리는 애들)
- recursive functions where more than one recursive call for each size of problem ex) Towers of Hanoi
- many important problems are inherently exponential
◦ unfortunate, as cost can be high
◦ will lead us to consider approximate solutions more quickly
def genSubsets(L):
res = []
if len(L) == 0:
return [[]] #list of empty list
smaller = genSubsets(L[:-1]) # all subsets without last element
extra = L[-1:] # create a list of just last element new = []
for small in smaller:
new.append(small+extra) # for all smaller solutions, add one with last element
return smaller+new # combine those with last element and those without
set of size k에는 2^k 개의 case가 있다
- but important to think about size of smaller
- know that for a set of size k there are 2k cases
- so to solve need 2n-1 + 2n-2 + ... +20 steps
- math tells us this is O(2^n)
👩💻 문제
✍️ 해설
2,3 번은 그냥 도는거니까 linear 이고,
4 번은 b/2를 하면서 루프를 반동강씩 내고 있으니까 로그해서 더 효율적이다 ?
리스트는 주소가 있고, 어디에 있는지 인덱스 정확히 아니까 괜찮은데,
Dictionary는 순서가 없으므로 찾고 저장하는 데 O(n) 시간이 걸린다.
| 시간 순서
O(1) < logn < n < n^c < c^n
| Search, Sort Algorithms
Brute force vs Bisection search
sorted list가 있으면 log 시간만에 bisection search를 할 수 있다!!
copying the list 는 constant 시간이 아니다. 더 오래걸린다.
당연히 sort하고나서 search를 하는게 log(n) 시간이 들어서 효율적이다. 한번만 할거면 필요없는데, 여러번 search를 할 경우에는 sort하는게 이득 !!
| Sorting Algorithms
def bogo_sort(L):
while not is_sorted(L):
random.shuffle(L)온갖 안좋은 이름 다 때려박은..ㅋㅋㅋ 안좋은 방법이지 당연히 랜덤이니까?
왼쪽에 있는 애들은 sort된 상태가 된다
ex) 키 작은 학생을 왼쪽에 넣고, 하나씩 다시 모두와 크기를 비교하는 거
2개씩 짝지어서 그 중에 작은애를 앞에 놓고, 그 다음에 다른 그룹이랑 묶어서 작은 애들끼리 비교해서 또 sort 하는 식
| Summary
- Application A:
- Every time it's asked to, it performs a linear search through list L to find whether it contains x.
- Application B:
- Sort list L once before doing anything else (using mergeSort). Whenever it's asked to find x in L, it performs a binary search on L.
Explanation:
Doing the search k times means that the time complexity is how long it takes to do mergeSort once, plus how long it takes to do a binary search k times. That works out to . Since we don't know what the value of k is, we cannot simplify further.
