복잡도

• O

  • 빅-오 라고 읽는다.

  • 점근적 상한에 대한 표기법.

  • O(g(n))은 g(n)의 증가율보다 작거나 같은 함수들의 집합이다.

    예를 들어 O(n2)에는 O(1),O(n),O(nlogn) 등이 포함된다.

    주어진 알고리즘의 증가율보다 크거나 같은 최소의 증가율을 찾는 것이 목적.

• Ω

  • 빅-오메가 라고 읽는다.
  • 점근적 하한에 대한 표기법.
  • 주어진 알고리즘의 증가율보다 작거나 같은 최대의 증가율을 찾는 것이 목적.

• Θ

  • 빅-세타 라고 읽는다.
  • 이 표기법은 주어진 함수(알고리즘)의 상한과 하한이 같은지 아닌지를 결정한다.
  • 세타(Θ) 표기법은 항상 상한(O)과 하한(Ω) 사이에 존재한다.
    • 상한과 하한이 같다면, 세타 표기법도 같은 증가율을 갖는다.

• 빅오가 최고 오래걸리는 상태라고 보면되고, 오메가는 적게 걸릴 때, 세타는 그 둘이 같을 때라고 보면 될 것 같다.

• 시간 복잡도 & 공간 복잡도

  • 시간 복잡도는 몇 번 실행하냐?
  • 공간 복잡도는 얼마만큼의 공간을 사용해야하나?
    • 고정공간 + 가변 공간으로 이루어져 있는데, 가변 공간을 얼만큼 사용하냐에 따라 복잡도가 나뉨.

연속 배열과 링크드 리스트의 차이점.

배열과 링크드 리스트의 가장 큰 차이는 삽입과 삭제를 할 때 이루어지는 것 같다.

어느 특정 위치에 삽입하는 경우 배열은 삽입 후 뒤의 배열을 붙이는 식으로 계산을 해야해서 오래걸리는 것 같고, 지우는 것도 해당 인덱스의 값이 없어지면 뒤에 있는 배열을 모두 땡겨줘야하기 때문에 오래걸린다.

하지만, 링크드 리스트의 경우 삽입 , 삭제 후 앞 뒤의 데이터의 이동 없이 연결만 시켜주면 되기 때문에 시간이 더 적게 걸린다.

데이터가 맨 끝에 삽입되고 삭제되는 경우가 아니라면, 보통의 경우 링크드 리스트가 훨씬 빠를 것 같다.

링크드 리스트에 추가할 때 걸리는 시간 복잡도는 방법에 따라 차이가 있다.

1. 맨 마지막에 추가하는 경우.

   tail 변수를 둬서 맨 마지막에 있는 node만 알고있다면 O(1)밖에 걸리지 않는다.

2. 중간에 추가하는 경우.

   head부터 모두 살펴봐야하기 때문에 O(N)만큼 걸린다.

3. 맨 앞에 추가하는 경우

   head에 추가하고 연결해주기 때문에 O(1)만큼 걸린다.

링크드 리스트에서의 탐색과 삭제.

특별히 탐색과 삭제는 탐색 후 삭제해야하기 때문에 O(N)만큼 걸리는 것 같다.

하지만 추가의 경우와 같이 head,tail이 존재한다면 맨 앞과 맨 뒤의 삭제시간은 O(1)이다.