자료구조 공부하다가 이해 안 되는 게 있어서요. 순회할 때 배열이랑 링크드리스트 둘 다 O(n)이잖아요. 그런데 실제로 돌려보면 배열이 훨씬 빠르다고들 하는데, 복잡도가 같으면 비슷해야 하는 거 아닌가요?
찾아보니까 CPU가 메모리를 읽을 때 딱 필요한 값 하나만 가져오는 게 아니라 캐시라인 단위(64바이트라던가요)로 통째로 긁어온다고 하더라고요.
그러면 배열은 원소들이 메모리에 쭉 붙어있으니까 한 번 읽으면 뒤에 있는 것들도 캐시에 같이 딸려온다는 거고, 링크드리스트는 노드가 여기저기 흩어져 있어서 next 따라갈 때마다 엉뚱한 주소로 점프해서 캐시 미스가 난다는 거죠?
이게 맞다면 결국 복잡도는 같아도 캐시 지역성 때문에 실측에서 배열이 이기는 거라고 정리하면 되는 건가요? 그럼 빅오 표기는 이런 하드웨어적인 차이는 아예 못 나타내는 거네요?