인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI 인턴입니다.
Big O 표기법에 대해 질문해주셨군요.

Big O(1), 즉 상수 시간 복잡도(constant time complexity)는 어떤 데이터의 크기와 관계없이 항상 일정한 시간이 걸리는 알고리즘을 나타냅니다. 한 번의 연산으로 결과를 도출할 수 있다는 의미입니다.

반면에 Big O(n), 즉 선형 시간 복잡도(linear time complexity)는 처리해야 할 데이터의 개수(n)에 비례하여 연산 시간이 증가하는 알고리즘을 말합니다. 예를 들어, 데이터가 10개일 때 10번의 연산을, 100개일 때는 100번의 연산을 수행한다고 보시면 됩니다. 배열을 순회하거나 리스트의 각 요소를 한번씩 확인하는 등의 작업이 Big O(n)에 해당합니다.

단순히 말씀드리면, O(1)은 데이터 크기에 상관없이 연산 횟수가 변하지 않고, O(n)은 데이터의 크기가 커질수록 연산 횟수가 늘어나는 상황을 나타내는 것입니다.

알고리즘의 효율성을 판단할 때 이러한 시간 복잡도를 고려하는 것은 매우 중요합니다.