학문
14살꿈많던아이
알고리즘의 시간복잡도는 왜 빅오 표기법으로 나타내나요?
프로그래밍을 배우는데 알고리즘 효율성을 O(n), O(log n) 같은 빅오 표기법으로 나타낸다고 해요. 정확한 실행시간이 아니라 왜 이런 근사적인 표기법을 쓰는지 궁금합니다.
5개의 답변이 있어요!
안녕하세요.
빅오 표기법은 컴퓨터 성능이나 프로그램 환경이 달라도 알고리즘이 입력 크기에 따라 얼마나 느려지는지를 쉽게 비교하기 위해 사용해요.
적어 주신 2개를 보면 O(n)은 데이터가 2배가 되면 처리량도 약 2배정도 늘어나는 성장 경향을 보여주죠.
실제 실행시간은 CPU 성능이나 프로그래밍 언어, 운영체제 등에 따라 달라지기 때문에 특정 컴퓨터에서 측정한 시간만으로는 알고리즘 자체를 비교하기는 어려워요.
그래서 빅오는 실행시간의 정확한 초 단위 값을 나타내기보다 입력 크기가 커질 대 필요한 연산량이 어떻게 증가하는지를 보는 거에요.
감사합니다.
채택 보상으로 436베리 받았어요.
채택된 답변안녕하세요. 강세훈 전문가입니다.
빅오 표기법은 컴퓨터 성능,언어,환경에 따라 달라지는 정확한 실행시간 대신
입력 데이터가 커질 때 연산량이 어떤 비율로 증가하는지를 나타내기 위해 사용합니다.
환경과 무관하게 알고리즘 자체의 효율성을 비교할 수 있는 공통 기준이랍니다.
안녕하세요. 박재화 전문가입니다.
빅오 표기법은 정확한 실행시간보다 입력 데이터가 커질 때 계산량이 얼마나 빠르게 증가하는지를 나타내기 위해 사용되는 것입니다. 실제 실행시간은 CPU 성능과 프로그래밍 언어, 메모리 상태 등에 따라 달라지기 때문에 초 단위로 비교하기가 어렵습니다.
O(n)은 데이터가 2배가 되면 필요한 계산도 대략 2배로 증가하는 형태를 의미하고, O(log n)은 데이터가 크게 늘어나도 계산량이 비교적 조금만 증가하기 때문에 매우 효율적인 편으로 볼 수 있습니다. 빅오에서는 작은 상수나 영향이 적은 계산은 제외하고는 데이터가 커졌을 때 가장 크게 영향을 주는 증가 형태를 봅니다.
결국에는 빅오 표기법은 서로 다른 컴퓨터에서도 알고리즘 자체의 효율성을 공통된 기준으로 비교하기 위한 방법으로 생각하시면 되겠습니다.
안녕하세요. 이수민 전문가입니다.
정확한 실행시간이 오히려 쓸모없는 숫자라서 그래요. 같은 코드도 컴퓨터 성능, 프로그래밍 언어, 그날의 시스템 상태에 따라 실행시간이 제각각이에요. 내 노트북에서 3초 걸린 코드가 서버에서는 0.1초일 수 있으니, 초 단위 시간은 알고리즘 자체의 성질이 아니라 환경의 성질인 거예요. 알고리즘끼리 공정하게 비교하려면 환경과 무관한 잣대가 필요했던 거죠.
빅오가 재는 건 데이터가 늘어날 때 일의 양이 어떤 비율로 불어나느냐예요. 데이터가 10배 되면 일도 10배 늘어나는 게 O(n), 100배로 폭증하는 게 O(n²), 몇 번 더 하는 수준에서 끝나는 게 O(log n)이에요. 이 증가 추세는 어떤 컴퓨터에서 돌려도 변하지 않는 알고리즘 고유의 성격이에요. 그리고 데이터가 커지면 세부 차이는 의미가 없어져요. 정확히 3n+5번 연산하든 2n번 하든, n이 백만쯤 되면 둘 다 그냥 n에 비례하는 부류거든요. 그래서 계수와 잔챙이 항을 버리고 큰 흐름만 남기는 거예요.
실무 감각으로 보면 빅오는 이 알고리즘이 데이터 커질 때 버틸 수 있는가라는 질문에 대한 답이에요. 회원 천 명일 때 멀쩡하던 기능이 백만 명이 되자 서버가 뻗는 사고의 원인이 대부분 O(n²)짜리 코드예요. 코딩테스트에서 빅오를 묻는 것도 큰 입력에서 살아남는 코드를 짤 줄 아는지 보려는 거라, 근사적이라서 부정확한 게 아니라 근사했기 때문에 본질만 남은 표기법이라고 이해하시면 돼요 :)
안녕하세요. 김재훈 전문가입니다.
알고리즘 실행 시간은 하드웨어 성능ㅈ프로그래밍 언어 컴파일러 및 실행 환경에 따라 매번 달라지므로 초 단위의 절대적인 측정값을 기준으로 삼기 어렵습니다 빅오 표기법은 이러한 외부 환경 변수를 배제하고 입력 데이터 크기의 증가에 따른 연산 횟수의 비례적 증가 추이만을 계량화하여 알고리즘 본연의 효율성을 객관적으로 비교하게 해줍니다. 또한 데이터가 극도로 커지는 최악의 경우에서 차수가 가장 높은 상한선만 남기고 하위 항과 상수를 생략함으로써 복잡한 계산 과정을 단순 명료하게 표현할 수 있습니다 결과적으로 개발자는 정밀한 시간 계산 없이도 다양한 알고리즘의 확장성과 점근적 성능 한계를 직관적으로 판단하여 최적의 솔루션을 선택할 수 있습니다