[알고리즘 기초] 시간복잡도, 자료구조

배열

삽입삭제는 느리고 조회는 빠르다

• 배열의 인덱스를 지정하여 한 삽입삭제의 시간복잡도 : O(n)
• insert() 는 느린 연산이다.
• 마지막에 추가하는 시간복잡도 O(1)
• append()
• 조회 → 임의접근이 가능하기 때문에 속도가 빠름 O(1)
• 임의 접근 : 인덱스값이 있기에

 

 

연결리스트

배열과 반대

삽입삭제는 빠르고 조회는 느리다

• insert() → O(1)
• delete() → O(1)
• 임의접근이 가능하지 않음 (어디있는 지 보장할 수 없어서)
• 처음 노드가 다음 노드의 주소값을 가지고 있기에

 

 

스택

선입후출 , 후입선출

들어가는 순서와 나가는 순서가 반대

마지막으로 들어온 게 제일 처음으로 나간다

• 삽입삭제 → O(1)
• 무조건 맨위의 값이 나가고 들어올때도 마지막으로 들어오기 때문에

 

 

큐

스택의 반대

선입선출, 후입후출

순서대로 들어오고 순서대로 나감!

먼저 들어온 데이터가 먼저 나감, 마지막에 들어온 데이터가 마지막에 나감

ex) 놀이공원, 맛집에 줄서기 (줄선순서대로 들어간다)

삽입을하면 맨뒤로 삽입이 되고 삭제는 제일 처음것이 삭제된다.

 

 

덱

양쪽으로 가능한 큐라고 생각하면 된다

맨앞 맨뒤 삽입삭제 가능하다

 

 

우선순위 큐

노드에 어떤 것이든 담을 수 있음

• 단, 노드 간에 우선순위가 정해져야 한다
• 정렬 기준이 있어야 한다
• 정렬 : 문자열(알파벳순), 숫자(크기순)

삽입은 알아서 되고 삭제는 우선순위가 가장 큰 애가 삭제 된다

삽입이 된다고 해서 정렬이 되어있지는 않음 (나는 루트노드만 알고 루트노드만 접근할 수 있음)

 

 

맵

딕셔너리 = 맵

키-밸류 쌍으로 데이터를 저장

• 삽입삭제조회 → O(1)삭제 : 키라는 곳을 삭제
• 삽입 : 키라는 곳에 벨류 값을 삽입

해시맵과 트리맵이 존재, 시간복잡도는 다름

출력은 순서를 알 수 없음 (뭐가 먼저 나올 지 랜덤이다)!!!!!

보통은 넣은 순서대로 나오는 거긴 한데 보장이 되지 않음 (해시맵이기 때문에 해시의 특징)

 

 

집합 Set

데이터들을 중복 허용하지 않고 저장

집합에서의 비트연산자 → 교집합 합집합

• 삽입삭제조회 → O(1)
• 크기를 조회하는 연산 → O(1)

요소들의 출력 순서는 알 수 없음 (해시 구조상 ..)