요즘 컴퓨터의 속도로는 1초에 10억번도 거뜬합니다. 플로이드 같이 연산이 간단하고 캐시 히트율이 높은 알고리즘이라면 더욱 그렇습니다.

보통 1억번을 1초라고 생각해왔는데 혼란이 오네요..

그럼,

캐시히트율이 낮은 1억번의 경우는 그렇지 않을 수도 있다는 말씀이신가요?

그냥, 그걸 정확히 측정하는 것은 매우 어렵다고 생각하시면 됩니다. 시간 복잡도라는 건 매우 대략적인 점근적인 측정만 하는 것이고, 실제로 연산의 수행 횟수가 몇 번인지, 하나의 연산은 CPU 명령 몇 개로 바뀌는지, 메모리 접근같이 무거운 연산이 얼마나 되는지, 파이프라이닝은 잘 되는지, 컴파일러가 어떻게 최적화를 해주는지 등 우리가 정확히 측정할 수 없는 요소가 너무나 많기 때문입니다. 1억번을 1초라 계산하는 건 알고리즘 문제를 풀면서 계산하는 시간 복잡도를 그 정도로 아~~~~주 대충 잡으면 거의 통과될 수 있다고 보는 기준일 뿐입니다.