TIL: 중첩된 for/while 루프는 어떤 경우에는 O(N)의 시간 복잡성을 가질 수 있습니다 (기술 면접을 위한 DSA)

파이썬에서 중첩 루프의 시간 복잡도는 루프의 구조에 따라 달라집니다. for 루프 안에 while 루프가 있는 경우에도 특정 경우에 O(N) 복잡도를 가질 수 있습니다. 첫 번째 예제에서 while 루프는 for 루프의 각 반복마다 한 번씩만 실행되며 상수 시간의 작업을 수행하여 O(N) 복잡도를 가집니다. 두 번째 예제에서 while 루프는 for 루프의 각 반복마다 일정한 횟수만큼 실행되어 다시 O(N) 복잡도를 가집니다. 세 번째 예제에서 while 루프의 조건은 변수가 총 N까지만 증가할 수 있음을 의미하여 O(N) 복잡도를 가집니다. 핵심은 내부 while 루프의 반복 횟수가 외부 for 루프와 독립적이면 결합된 복잡도가 여전히 O(N)일 수 있다는 것입니다. 내부 while 루프가 외부 for 루프의 각 반복마다 N번 실행되는 경우에만 복잡도가 O(N^2)가 됩니다. O(N^2) 복잡도의 예는 while 루프가 for 루프의 각 반복마다 N번 실행되는 경우입니다. 이 경우 for 루프는 N번 실행되고 while 루프는 for 루프의 각 반복마다 N번 실행되어 O(N^2) 복잡도를 가집니다. 중첩 루프의 구조가 전체 시간 복잡도를 결정합니다.