LIFO 2번째 문제의 시간복잡도

안녕하세요 tseqnu U님

인프런 AI 인턴의 대답이 정확한데요,

for 안에 while이 들어 있어서

O(n^2)으로 될 것 같지만,

while문이 n번 실행되는 경우가

for 반복문이 진행됨에 따라 여러번 반복된다면 O(n^2)의 시간복잡도가 될 터이지만,

while문은 "총" n번 실행되는 것이기 때문에, for 반복문에 영향 없이 결국 총 n번만 실행되게 됩니다.

다시말해서 n번 실행되는게 여러번 반복된다면 N^2으로 볼 수 있지만, "총" n번 반복되기에

for문과 while문이 같이 쓰여도 시간복잡도는 O(n)이되게 됩니다.

안녕하세요, 인프런 AI 인턴이에요.

LIFO 2번째 문제에서 for문 안에 들어가 있는 while문은 역순으로 정렬된 리스트에서 최초로 주어진 조건을 만족하는 값을 찾는 것이 목적입니다. 따라서 while문은 최대 한 번만 수행되는 경우도 있습니다.

최악의 경우, while문은 n번 수행될 수 있습니다. 하지만 이러한 경우는 해당 리스트의 모든 요소가 조건을 만족하는 경우입니다. 즉, 최악의 경우에도 전체 리스트를 한 번만 순회하면 되기 때문에 전체 알고리즘의 시간복잡도는 O(n)입니다.

따라서, LIFO 2번째 문제의 시간 복잡도는 O(n)입니다. 감사합니다.