빅 O 표기법이란 무엇인가요?
질문: 빅 O 표기법이란 무엇인가요?
A: 빅 O 표기법은 서로 다른 함수의 증가율을 비교하는 방법으로, 완료하는 데 걸리는 메모리와 시간을 계산하여 서로 다른 알고리즘의 효율성을 비교하는 데 자주 사용됩니다. 또한 문제가 얼마나 복잡한지 파악하는 데에도 사용할 수 있습니다.
질문: 이 표기법을 최초로 사용한 사람은 누구인가요?
A: 수학자 폴 바흐만(1837-1920)이 1896년 그의 저서 "분석적 해석학"에서 이 표기법을 최초로 사용했습니다.
질문: Big O는 무엇을 의미하나요?
A: Big O는 "함수의 순서"를 의미하며 함수의 증가율을 나타냅니다.
질문: Big O는 어떻게 사용되나요?
답변: Big O 표기법은 함수의 성장률에 대한 상한(가능한 최대값)을 찾는 데 사용되며, 이는 입력값을 출력값으로 바꾸는 데 걸리는 최장 시간을 계산하는 데 사용됩니다. 즉, 매번 가장 긴 경로를 사용하는 최악의 시나리오에서 소요되는 시간에 따라 알고리즘을 그룹화할 수 있습니다.
질문: 랜도 심볼이란 무엇인가요?
A: 랜도 기호는 이 표기법을 대중화시킨 에드먼드 랜도(1877~1938)의 이름을 딴 빅 O 표기법을 말합니다.
질문: 빅 O가 유용한 이유는 무엇인가요?
A: Big O는 항상 최악의 시나리오를 가정하기 때문에 컴퓨터에서 프로그램을 실행하지 않고도 속도를 측정할 수 있으며, 컴퓨터 간의 하드웨어 차이에 관계없이 일관성을 유지합니다. 또한 컴퓨터에서 알고리즘을 실제로 실행하지 않고도 알고리즘이 얼마나 효율적인지 보여줍니다.
