내배캠 TIL 9일차 (공간복잡도와 링크드리스트)

공간복잡도

 

내가 알던 것 - 의미없다

정리하면서 안 것 - 다 메모리 기술 발전 덕이다, 아주 중요하던 시절은 이와타 사토루 SFC 깎던 시절 이야기

 

def largest_product(my_list):

    products = []

  for a in my_list:

    for b in my_list:

    # products 배열에 원소가 들어가는 이 연산은 (a * b)번이 실행되겠죠? 2중 루프!

      products.append(a * b)

  return max(products) # 따라서, products의 공간 복잡도는 O(N^2)

가 주어진 예시

 

깊숙히 찾다가 가변공간, 고정공간 개념을 배웠는데

 

가변= 알고리즘 실행과 관련있는 공간으로실행 중 동적으로 필요한 공간 (문제의 인스턴스에 따라 가변적인 메모리 공간)

고정= 알고리즘과 무관한 변수,상수,코드저장

 

 

링크드리스트- 중요한건 내일 함

 

배열과 비슷하나 원소의 삽입.삭제가 장점

배열은 좀더 속도가 빠르고 값을 가져옴

 

반대로 링크드는 값을 조회하는데 나약하다

특정 노드(리스트의 원소)로 가려면 노드 전체 배열의 순서를 타고와랴 한다

일일히 방문하는 만큼 상대적으로 느림

 

시간복잡도는 배열이 O(1) 링크드리스트가 O(N)