질문
1주차 Day2에 시간복잡도에서 Big-O 표기법에 대해 질문 있습니다! 검색해보니 알고리즘의 시간복잡도는 반복문에 의해 결정된다고 보았습니다.
그럼 반복문을 아예 사용하지 않으면 시간 복잡도가 O(n)이라고 보면 되는 걸까요? 프로토타입 자료구조를 갖고서는 Big-O를 어떻게 계산하는지가 궁금합니다.
답변
반복문을 사용하지 않을 경우에도 시간복잡도는 로직에 따라 달라질 수 있습니다. 만약 O(1)짜리 작업을 n번 수행하면 O(n)이 됩니다. 예를 들어,
1+1 연산을 n * n번 반복하면 시간복잡도가 O(n^2)이 될 수 있어요. 🙂