20220802 TIL

시간복잡도라는 개념을 우리가 쓰는이유

⇒ 시간과의 상관관계를 이해하고 싶어서

• N이 40이면 40X40의 시간이 걸린다는걸 알고싶은거지, 1600이 알고싶은것이 아님
• 그래서 이걸 수식으로 표현해야 올바른 알고리즘의 시간복잡도 분석이 가능하다

빅오표기법 왜 쓸까?

• 알고리즘은 입력값의 분포에 따라서 성능이 변화할 수 있음
• 대부분의 입력값은 최선일 경우가 없음. 우리는 항상 최악의 경우를 대비해야 하기 때문에 모든 알고리즘을 빅오 표기법으로 분석하는 것

---

기억할것

1. 입력값에 비례해서 얼마나 늘어날지 파악해보자 N? N제곱?
2. 공간복잡도보다는 시간복잡도를 더 줄이자
3. 최악의 경우에 시간이 얼마나 걸릴지 (빅오표기법)에 대해 고민하자

 

---

소수 구하는 함수가 있을줄알았는데,

에라스토스의 체를 통해 풀 수 있고, 이것도 좀 더 향상시키는 방법이 있다고 함(see below)

1. 2부터 수의 제곱근까지 나누어보는 방법

def isPrime(n): for i in range(2, int(n**0.5)+1): if n % i == 0: return False return True

​

2. 2부터 수의 제곱근까지 나누어보는 방법+홀수만 검사

def isPrime2(n): if n==2 or n==3: return True if n%2==0 or n<2: return False for i in range(3, int(n**0.5)+1, 2): # only odd numbers if n%i==0: return False return True

​

두번째방법이 약 30%의 속도향상이 있다고하네요

​

[출처] 파이썬 소수 체크|작성자 용용

---

한번씩 들어서는 이해하지 못하는 것들이 넘많문