코딩쌀롱

배열과 링크드 리스트의 비교에서 싱글 링크드 리스트라는 전제 하에 작성하였습니다. 링크드 리스트(Linked List) 메모리는 데이터 조각을 저장하는 셀들의 거대한 집합 같은 형태로 이루어져 있다. 배열 - 연속된 빈 셀 그룹에 데이터를 저장 링크드 리스트 - 인접하지 않은 메모리 셀 묶음 링크드 리스트는 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 링크드 리스트가 배열보다 나은 점 중 하나로 프로그램이 데이터를 저장하기 위해 메모리 내에 나란히 이어진 빈 셀 묶음을 찾을 필요가 없다는 것이다. 프로그램은 서로 인접하지 않은 여러 셀에 걸쳐 데이터를 저장할 수 있다. 링크드 리스트의 서로 인접하지 않은 이러한 셀을 '노드'라고 한다. 각 노드는 노드에 저장된 데이터뿐만 아니라 연결 리스트 내에 ..

점근적 표기법(Asymptotic notation) 빅 오 표기법 (big O) 시간의 상한 (최악의 시나리오) 최악의 경우에도 big O를 넘지 않는다. 빅 오메가 표기법 (big Ω) 시간의 하한 (최선의 시나리오) 아무리 빨라도 big Ω보다 빠를 수 없다. 빅 세타 표기법 (big θ) 평균적인 경우 (big O ~ big Ω) 빅 오 표기법(big O notation) 빅 오 표기법은 알고리즘 간 차이를 드러내고 주어진 상황에 알맞은 알고리즘을 결정하게 해주는 훌륭한 도구이다. 빅 오를 사용하면 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 기회가 생기며 "이 알고리즘이 일반적으로 쓰이는 알고리즘만큼 빠른가 혹은 느린가?"라고 자문해 볼 수 있다. 빅 오 표기법은 알고리즘에 얼마나..