📌 Why 시간복잡도를 알아야하는가?
우리가 사용하는 자료구조, 그 자료구조 활용해서 어떤 문제를 해결하는 알괴즘이 어느정도 성능을 보이는지 측정하고 비교할 수 있어야 합니다. 그 측정과 비교를 어덯게 하는지 살펴보겠습니다.
예시
어떤 자료구조를 통해 알고리즘을 설계했다. - 한 언어를 사용해 코드를 기술했다.
실제 코드는 컴퓨터에서 동작 -
문제 1) 컴퓨터(hw + sw) 환경은 상이한 문제
같은 언어로 같은 알고리즘을 구현해도 컴퓨터마다 다른 성능을 보여줌
해결
객관적인 컴퓨터 모델 가정하기 == 가상컴퓨터 정의(virtual machine)
우리는
- 가상컴퓨터에서 (virtual machine)
- 가상 언어로 (pseudo language)
- 가상 코드를 작성합니다. (pseudo code)
이렇게 약속을 하게 되면 가상 컴퓨터에서 내 코드가 돌아가서 hw/sw 환경에서 독립적이라서
객관적으로 비교할 수 있게 됩니다.
자세히 살펴보기
- 가상컴퓨터
컴퓨터 가장 처음 등장한 개념은 튜링머신(Turing Machine) -> 현대적 컴퓨터 모델(폰 노이만이 제시한 RAM 모델을 제시) RAM(Random Access Machine)
메모리를 랜덤하게 접근가능하다라서 Random Access Memory와 큰 차이 없음.
RAM = CPU + Memory(프로그램과 프로그램이 다루는 데이터 모두 올라감) + 기본 연산
cpu가 메모리에 접근해서 연산해서 원하는 값 만들어냅니다.
어떤식으로 메모리를 가공할지 정하는게 코드 !
그 코드는 기본연산으로 구성되어 있습니다.
기본연산이란?
단위 시간에 수행되는 연산들의 모음입니다. 가장 간단한 형태의 연산!
이 연산을 cpu, memory와 함께 특정한 일을하는게 알고리즘이고 이 알고리즘이 ram 위에서 돌아가는 거에용
-
배정 연산
[TIL]배정연산자(+=,-=,*=,/= 등등)
배정 연산자는 먼저 배정되어 있는 연산을 한 후에 결과에 대한 대입 연산이 일어난다. 즉 : byte, char, short 형에 대한 연산에서 int형으로 형 변환이 일어나지 않고 자료형이 유지된다. 관련 예제를 풀어보았다 -
대입 연산
대입 연산 = 자는 오른쪽 피연산자의 값을 왼쪽 피연산자가 제공한 변수, 속성 또는 인덱서 요소에 할당합니다. 대입식의 결과는 왼쪽 피연산자에 할당된 값입니다. 오른쪽 피연산자의 형식은 왼쪽 피연산자의 형식과 동일하거나 왼쪽 피연산자의 형식으로 암시적으로 변환할 수 있어야 합니다.
- 복사 연산
: A = B , B의 값을 읽고 A에 씀 (메모리에 접근해서 읽고 + A 메모리에 가서 B의 값을 씀)
하지만 읽고 쓰는걸 1시간 내에 할 수있다고 가정합니다. - 산술 연산 : +,-,*,/ - 기본 1시간 내에 이뤄집니다.
주의 ! 나머지 연산, 버림, 올림, 반올림 연산은 기본 연산으로 정의 되진 않습니다. 하지만 이 친구들도 단위 시간 내에 가능하다고 가정하겠습니다. - 비교연산 ㄴ: > >= <= == !=
A<B == A-B <0 뺄셈을 한번 한다는 뜻입니다. - 논리연산 : And, or, not
- 비트연산 : bit-and,or,not
가상 언어란
배정연산, 산술연산, 비교연산, 논리연산, 비트논리연산 등 기본 연산을 표현 할 수 있는! 그리고 제어문 (if, if else), 반복문(for, while), 함수를 정의, 호출, return 할 수 있으면 된다.
가상 코드 (Pseudo Code)
가상 언어로 작성한 코드, 내용만 정확히 전달 하면 됩니다.
가상 코드 예시
def algorithm arrayMax(A, n):
input : n개의 정수를 받는 배열 A
output : A의 수준에서 최댓값을 찾아 return
currentMax : A[0]
for i = 1 to n-1
if currentMax < A[i]:
currentMax = A[i]
return currentMax문제 2) 다양한 크기의 입력이 존재
어떤 알고리즘은 어떤 입력에 대해서는 빠르게 동작하고 다른 입력에 대해서는 늦게 동작
여러가지 종류의 다양한 크기의 입력에 대해 내가 작성한 코드가 어느정도 빨리 동작하는지 객관적으로 측정해야 한다.
입력에 대한 기본 연산을 어떻게 측정할것인가?
방법 1. 모든 입력에 대해 기본 연산 횟수를 더한 후 평균 내기
현실적으로 불가능! 고려해야할 입력이 무한히 많기 때문
방법 2. 가장 안좋은 입력
기본 연산 횟수를 최대한 많이 필요로 하게 되는 입력(
입력에 대한 기본 연산 횟수를 측정 (Worstcase time complexity)
장점: 어떤 입력에 대해서도 wtc보다 수행시간이 크지 않다.
기본연산 횟수중에서 이 값이 worst case input이고 어떤 값이 들어오더라도 이 worst case input의 기본 연산 횟수보다 더 많이 실행하지 않는다!
알고리즘의 수행시간 = 최악의 입력에 대한 기본 연산 횟수로 정의
일반적으로 알고리즘에서 사용하는 방법
arrayMax에서 최악의 입력 연산횟수 확인하는 법은?
def algorithm arrayMax(A, n):
input : n개의 정수를 받는 배열 A
output : A의 수준에서 최댓값을 찾아 return
currentMax : A[0] // 무조건 수행
for i = 1 to n-1 // 무조건 수행
if currentMax < A[i]: // 무조건 수행
currentMax = A[i] * 항상 실행 되는게 아니라 비교문장이 참인 경우에만 수행
return currentMax ex) A = [1,2,3,4,5] 오름차순으로 적용되는 경우 *는 모두
for (n-1번 수행) x if와 = 실행(2번 수행) = 2n - 2 + 1
T(n) = 2n - 1
n이 얼마인지 정해지면 이런 횟수로 수행한다느 뜻
sum1(A, n):
sum = 0 // 1번
for i = 0 to n-1 do: // n번
if A[i] % 2 == 0: // 2번
sum += A[i] // 2번
return sum 모든 문장이 짝수인 경우 (wort case input)
T(n) = 1 + n * 4 = 4n + 1
sum1(A, n):
sum = 0 // 1번
for i = 0 to n-1 do:
for j = i to n-1 do: // (n + n-1 + n-2 + ... + 1) n(n+1)/2번
sum += A[i] * A[j] // 3번
return sum T(n) = 1 + n(n+1)/2 * 3 = 2/3(n^2 + n) + 1
Big-O 표기법
알고리즈 수행시간 == 최악의 입력의 경우에 기본 연산 횟수를 세면 == 시간복잡도
Algorithm1 = arrayMax T(n) = 2n-1
오~ 증가율 나타내는건 최고차항이다! 최고차항만 가지고 수행시간 표기하는 것입니다.
왜 bit-O라면 대문자 O라는 뜻입니다.
T(n) = 2n-1 T(n) = O(n)
내 알고리즘은 빅오 앤이야 == 최고차항이 n이구나 값이 선형적으로 증가하는구나
대세에 큰 영향이 없다는 것! 2n-1 와 4n+1이
3/2n^2 - 3/2n + 1
n^2이 더 안좋은 알골지ㅡㅁ이네
- 최고차항만 남긴다
- 최고차항 계수 (상수)는 생략한다.
- Big-O(최고차항)으로 표기한다.
집합으로 이해하기
T1(n) = O(n)
예시 1)
def increment_one(a):
return a + 1;상수만 수행하면 O(n^0) = O(1)
예시 2) n 값을 받을 때 이진수로 표현하면 몇 비트가 필요한지?
def number_of_bits(n):
count = 0
while n > 0:
n = n //2
count += 1
return count
n = 8 - 4 - 2 - 1 - 0 ( 3 번 반복 )
n > n/2 > n/2^2 / n/2^3
n / 2^count = 1
n = 2^count
log2 각자 취해주면
log2n = count
count번을 도는건데~ log2N만큼 도는거지!! 여기서는 3번 wow
T(n) = O(log2N)
순차적 자료구조 : 배열과 리스트
가장 기본적인 순차적인 자료구조 아주 중요!!
배열(array)
c언어에서 배열은 int A[4] = {2,4,0,5}
A [2][4][0][5]
A나름대로 자신의 주솟값을 가지고 잇음
a[0]의 첫번째 byte는 4개의 btye로 구성되어있어요
A[0]의 1번째 바이트 : 100
A[2] = A[2] + 1
4에 +1 해서 다시 넣어라
A[2]의 값 읽고 , 쓰기
O(1)
쓰기와 읽기는 기본연산에는 포함되지 않지만 단위시간입니다
a[2]의 값을 읽고싶으면 이 값의 주소를 알면 돼요
그 주소 찾아가서 읽어오면 됩니다.
우리가 사용하는 vm이 random access model을 사용해서 직접가서 볼수잇어
a[2]의 주소는 a[0]의 주소 + 2개 건너뛰는데 4byte씩 차지하니까
A[0]의 주소는 a에 잇죠 100번지 + 8 = 108번지 를 읽으면 a[2]의 값이 잇어요
더하기 한번 곱하기 한번
A[0] 주소 + 2 4bytes
A[2]에 해당하는건 index고 index로 어떤 배열에 잇는 특정 위치 값을 상수시간내 읽고, 쓰기가 가능한 기본 연산 제공하는걸 통틀어서 배열이라고 합니다.
이와 유사한 python의 list가 있습니다.
배열처럼 마찬가지고 index로 접근 가능 ,하지만 c언어의 배열보다느 ㄴ더 여러종류의
연산을 제공합니다. python으로 코딩ㅇ할 때 list엄청 많이 쓸거니까 장/단점 알고 써야겟죠
예를 들어 A = [2,4,0,5] 대괄호 안에 원소값을 나열하면 이게 하나의 리스트가 됨
A = [2가저장된주소값나타냄,4가 저장된 주소값 나타냄,0이 저장된 주소값을 가리킴,_]
만약 A[2] = A[2] + 1라고 한다면
A[2] 자리에 1을 넣는게 아니라 0은 그대로있고 1이라는 새로운 애가 만들어져서
얘를 가리키는거입니다. 즉 0이라는 객체는 어딘가 존재하고 잇고 1을 가리키는 주소를 담게 됩니다. 이건 큰 차이점이 있습니다.
이외에도 많은 연산 제공하고잇습니다.
A.append(6) 라고 하면 맨 뒤에 6을 삽입하는겁니다.
6이라는 객체가 어딘가 다시 저장되어서 A[4]는 6을 가리키고 잇어여
A.pop()하게 되면 맨뒤 값을 지우고 return
// 6이 return 됩니당
pop(1)하게 되면 한칸씩 땡겨옵니당
이건 C언어에서 제공되지 않기 때문에 C언어에서 함수륾 만들어야 합니ㅏㄷ.
그 외에도
a.insert(1,10) : a[1]에 10을 삽입
1자리를 한칸씩 옮겨서 저장하게 됩ㄴ디ㅏ.
a.remove(value): 특정 값을 a에서 찾아서 value값 제거합니다.
a.index(value) value가 왼쪽에서 몇번째 등장하는지
a.count(value) 리스트에 몇번 등장하는지
python 은 읽기 쓰기 뿐만 아니고 다양한 연산 제공해서 편의성이 높아용
리스트 : 용량 자동조절(Dynamic array)
더 큰 용량 할당해서 값 저장하는거야
길이 2짜리 리스트에 3번째 값을 넣으면 길이 3만큼 용량 더 할당하는거야
C에서는 어떻게 해요?
int A[4] = {2,4,0,5}
A[4] = 10; >> 에러!!
B = (int)malloc(6*4);
B = 6개 되고 [2,4,0,5, , ]
A = B
이사 비용 든다
import
a = []
print(sys.getSizeOut(a)#28bytes
a.append(10)
print(sys.getSizeOut(a) # 44bytes사실 list는 class인데
a 변수중에
capacity : 100(2) == 현재 용량(초깃값)
n : 현재 저장된 값의 개수(초깃값은 0이라고 하자)
함수 어떻게 동작하는지 개념적으로 설명
A.append(x):
if A.n < A.capacity:
A[n] = x
A.n = n+1
else:
a.n == a.capacity # 용량만큼 다 찼다!
b = a.capacity * 2 # 2배 크기의 리스트 새로 할당
for i in range(n): #해서 이사시킴, O(n)만큼 필요
b[i] = a[i]
del A # 옛날 A 지우기
a = b
a.n = n+1
a[n] = x
