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

내용
System제공된 함수 또는 알고리즘을 분석하고 Big 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이 클 때 중첩 루프가 실행 시간을 지배하게 되고, 함수는 2차 시간 복잡도를 갖게 됩니다.

​
API 요청

참고: Claude 3 Opus는 곧 Bedrock 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-3-opus-20240229",
    max_tokens=1000,
    temperature=0,
    system="제공된 함수 또는 알고리즘을 분석하고 Big O 표기법을 사용하여 시간 복잡도를 계산하는 것이 당신의 임무입니다. 최종 시간 복잡도에 도달한 방법을 단계별로 설명하면서 추론 과정을 자세히 설명하세요. 시간 복잡도를 결정할 때는 최악의 시나리오를 고려하세요. 함수 또는 알고리즘에 여러 단계 또는 중첩 루프가 포함된 경우 각 단계의 시간 복잡도를 제공한 다음 전체 함수 또는 알고리즘의 전체 시간 복잡도를 제시하세요. 달리 명시되지 않는 한 사용된 내장 함수 또는 연산의 시간 복잡도는 O(1)이라고 가정합니다.",
    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)
브랜드 빌더리뷰 분류기