시간 복잡도는 실제 수행 시간과 어떤 관계가 있는가?

[SeoYeonBae]

• 시간 복잡도와 입력 크기를 알고 있으면 알고리즘이 어떤 시간 안에 동작할지 대략 짐작이 가능
• 프로그램의 메모리 접근 패턴, CPU 명령어의 수 등 동작 속도에 영향을 끼치는 요소는 많음
• 그러나, 이들은 수행 속도를 몇 배 정도 차이나게 할 뿐!
• 알고리즘의 시간 복잡도는 달라지면 프로그램은 수천 배, 수만 배까지 빨라지거나 느려질 수 있음

[KangYoonjoo]

• 컴퓨터의 사양에 따라 처리 속도가 전부 다르므로, 실제 수행 시간을 구할 때는 보수적으로 보아야한다
• 따라서 시간복잡도는 보통 최악을 가정하고 산정한다
• cpu는 메모리에서 캐시로 데이터를 불러온 뒤 처리하므로, 메모리 사용 패턴이 복잡할 경우 실제 수행 속도에서 차이가 날 수 있다

[jangyejoo]

• 시간 복잡도를 알면 대략적인 실행 시간을 알 수 있음
• 하지만 컴퓨터 사양에 따라, 입력 크기에 따라 차이가 날 수 있음

[Han7sunny]

시간 복잡도

• 알고리즘의 수행 시간 기준
• 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대해 함수로 표현한 것
• 일반적으로 시간 복잡도가 작을수록 알고리즘은 빠르게 실행되고, 큰 입력에 대해 효율적으로 동작

하지만, 시간 복잡도가 낮다고 해서 항상 실제 수행시간이 낮은 것은 아니다.

• 컴퓨터의 하드웨어, 프로그래밍 언어, 컴파일러 최적화, 알고리즘의 구현 방식 등을 통해 알고리즘의 성능은 영향을 받는다.