2장. 효율적인 프로그램이란?
Updated:
#시간/공간 복잡도
- 효율성의 측정 방식
- 시간복잡도가 공간복잡도 보다 비교적 중요하다
시간 복잡도
- Time - complexity
- 코드가 얼마나 빠르게?
- 알고리즘에 사용되는 총 연산 횟수
- 실행시간 X 연산횟수 O
sum = 0 # 1
for i in [1, 2, 3, 4]:
sum +=i # 5
# 시간복잡도 = 5
randomNumber = 0 # 1
nums = [1, 2, 3, 4] # 1
for i in range(len(nums)):
for j in range(len(nums)):
randomNumber += nums[i] nums[j] # 4 * 4 = 16
# 시간복잡도 = 18
- 입력 변수의 크기 = N
- 코드의 시간복잡도 = f(N)
Big-O 시간 복잡도란
- Big-O => 시간복잡도 함수의 가장 높은 차수
- 계수 X => 시간복잡도에 미치는 영향이 매우 미미하다
- O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^N) < O(N!)
aN + b = O(N)
aNlogN + b = O(NlogN)
aN^2 + bN + c = O(N^2)
# nums의 크기는 N
def doNothing(nums):
return nums
# 시간 복잡도 = 1
# Big-O시간 복잡도 = O(1)
# nums의 크기는 N
def doSomething(nums):
sum = 0 # 1
for num in nums:
sum += num # N
return sum # 1
# 시간 복잡도 = N + 2
# Big-O시간 복잡도 = O(N)
# nums의 크기는 N
def doManything(nums):
allPairs = [] # 1
for i in range(len(nums)):
for j in range(lend(nums)): # N * N
if nums[i] < nums[j]: # 1
allPairs.append((nums[i], nums[j])) # 1
else:
allPairs.append((nums[i], nums[j]))
return allPairs # 1
# 시간 복잡도 = 2*N^2 + 2
# Big-O시간 복잡도 = O(N^2)
Big-O 시간 복잡도 계산법칙 1
- For / while loop가 한 번 중첩될 때마다 O(N)
for num in nums:
# O(N)
for i in range(len(nums)):
for j in range(len(nums)):
# O(N^2)
for i in range(len(nums)):
for j in range(len(nums)):
for k in range(len(nums)):
# O(N^3)
Big-O 시간 복잡도 계산법칙 1
- 자료구조 사용, 다른 함수 호출에서 각각의 O(N)을 파악
nums = [2, 8, 19, 37, 4, 5]
if num in nums:
# O(N)
nums = {2, 8, 19, 37, 4, 5}
if num in nums:
# O(1)
nums.sort()
# O(NlogN)
Big-O 시간 복잡도 계산법칙 1
- 매번 절반씩 입력값이 줄어들면 O(logN)
- 이진탐색 (N = 8, 실행횟수 = log(8) = 3)
공간 복잡도
- Space - Complexity
- 알고리즘에 사용되는 메모리 공간의 총량
- 얼마나 많은 메모리를 사용?
a = 1
# O(1)
a = [num for num in nums]
# O(N)
a = [[num for num in nums] for num in nums]
# O(N^2)
배열
- 가장 기본적인 자료 구조
nums = [1, 2, 3, 4, 5, 6]
배열 : Big-O 시간 복잡도
- 인덱스를 알 때 : O(1)
- nums[2]
- 인덱스를 모를 때 : O(N)
- if 5 in nums:
- 배열 전부 순회하기 : O(N)
- for num in nums:
- 자료 끝에 추가하기 : O(N)
- nums.append(7)
- 자요 중간에 추가하기 : O(N)
- nums.insert(3, 9)
- 중간에 추가하면 뒤의 값을 밀어주어야하기 때문에 O(N)
배열 인덱싱
- nums[2]
- nums[2:5]
- nums[len(nums)-1]
- nums[-1]
배열 : Big-O 공간 복잡도
- 배열의 공간 복잡도 = O(N)
문자열
- 배열의 한 종류, 문자들의 배열
tempString = "abcdef"
for ch in tempString:
2차원 배열
nums = [[1,2,3,4,5],
[6,7,8,9,10],
[11,12,13,14,15],
[16,17,18,19,20]]
해쉬
- Dictionary.Key + Value(in Python)
- Key는 중복될 수 없음
- 공간 복잡도는 대략 O(N)
studentIds = {
"박지나" : 123,
"송호준" : 145,
"이주원" : 563
}
해쉬 : Big-O 시간 복잡도
- Key를 이용해서 Value 가져오기 : 대략 O(1)
print(strudentIds["박지나"])
- Key가 존재하는 확인하기 : 대략 O(1)
if("박지나" in studentIds):
if("손지윤" in studentIds):
- key, Value 추가하기 : 대략 O(1)
studentIds['손지윤'] = 938
- 해당 key의 Value 변경하기 : 대략 O(1)
studentIds["박지나"] = 555
해쉬 공간 복잡도
- 해쉬의 공간 복잡도 = O(N)
- 해쉬는 데이터가 입력되지 않은 여유 공간이 많아야 성능 유지 -> 데이터간의 충돌 방지
Set
- Value 없이 Key만 있는 Dictionary
- 중복을 허용하지 않는다
studentNames = {'박지나', '송호준', '이주원', '손지윤'}
배열과 해쉬의 trade-off
- trade-off : 하나를 얻기 위해 다른 하나를 포기해야한다.
배열 VS 해쉬
- 해쉬 : 식별자가 있는 데이터, 시간 복잡도↓ / 공간 복잡도↑
- 배열 : 식별자가 없는 데이터, 시간 복잡도↑ / 공간 복잡도↓
Leave a comment