직접 시도해보려면 이 프롬프트를 개발자 Console에 복사하세요!

내용
System제공된 함수나 알고리즘을 분석하고 빅 O 표기법을 사용하여 시간 복잡도를 계산하는 것이 당신의 임무입니다. 최종 시간 복잡도에 도달한 방법을 단계별로 설명하며 추론 과정을 설명하세요. 시간 복잡도를 결정할 때 최악의 경우 시나리오를 고려하세요. 함수나 알고리즘에 여러 단계나 중첩된 루프가 포함된 경우, 각 단계의 시간 복잡도를 제공한 다음 전체 함수나 알고리즘에 대한 전체 시간 복잡도를 제시하세요. 달리 명시되지 않는 한 사용된 모든 내장 함수나 연산의 시간 복잡도는 O(1)이라고 가정하세요.
Userdef example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k)

​
예시 출력

주어진 함수 example_function(n)의 시간 복잡도를 분석하기 위해, 단계별로 나누어 최악의 경우 시나리오를 고려해 보겠습니다.

1단계: 첫 번째 루프 분석

for i in range(n):
   print(i)

이 루프는 n번 반복하며 각 반복에서 상수 시간 연산(print(i))을 수행합니다. 따라서 이 단계의 시간 복잡도는 O(n)입니다.

2단계: 중첩된 루프 분석

for j in range(n):
    for k in range(n):
        print(j, k)

외부 루프는 n번 반복하고, 각 반복마다 내부 루프도 n번 반복합니다. 내부 루프의 각 반복에서는 상수 시간 연산(print(j, k))이 수행됩니다. 따라서 중첩된 루프의 시간 복잡도는 O(n * n) = O(n^2)입니다.

3단계: 시간 복잡도 결합
example_function(n) 함수는 두 단계로 구성됩니다: 첫 번째 루프와 중첩된 루프. 전체 시간 복잡도는 각 단계의 시간 복잡도의 합입니다.

첫 번째 루프의 시간 복잡도: O(n)
중첩된 루프의 시간 복잡도: O(n^2)

전체 시간 복잡도를 결정하기 위해, 가장 높은 성장 차수를 가진 지배적인 항을 고려합니다. 이 경우, O(n^2)가 O(n)을 지배합니다.

따라서, example_function(n) 함수의 전체 시간 복잡도는 O(n^2)입니다.

최악의 경우 시나리오에서, n이 클 때, 중첩된 루프가 실행 시간을 지배하게 되며, 함수는 이차 시간 복잡도를 갖게 됩니다.

​
API 요청

import anthropic

client = anthropic.Anthropic(
    # defaults to os.environ.get("ANTHROPIC_API_KEY")
    api_key="my_api_key",
)
message = client.messages.create(
    model="claude-opus-4-20250514",
    max_tokens=1000,
    temperature=0,
    system="Your task is to analyze the provided function or algorithm and calculate its time complexity using Big O notation. Explain your reasoning step by step, describing how you arrived at the final time complexity. Consider the worst-case scenario when determining the time complexity. If the function or algorithm contains multiple steps or nested loops, provide the time complexity for each step and then give the overall time complexity for the entire function or algorithm. Assume any built-in functions or operations used have a time complexity of O(1) unless otherwise specified.",
    messages=[
        {
            "role": "user",
            "content": [
                {
                    "type": "text",
                    "text": "def example_function(n):\n    for i in range(n):\n        print(i)\n\n    for j in range(n):\n        for k in range(n):\n            print(j, k)"
                }
            ]
        }
    ]
)
print(message.content)