프롬프트 라이브러리

효율성 추정기

함수와 알고리즘의 시간 복잡도를 계산합니다.

이 프롬프트를 개발자 Console에 복사하여 직접 사용해 보세요!

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

내용

System

제공된 함수 또는 알고리즘을 분석하고 Big O 표기법을 사용하여 시간 복잡도를 계산하는 것이 당신의 과제입니다. 최종 시간 복잡도에 도달한 과정을 단계별로 설명하세요. 시간 복잡도를 결정할 때 최악의 시나리오를 고려하세요. 함수 또는 알고리즘에 여러 단계나 중첩 루프가 포함된 경우, 각 단계의 시간 복잡도를 제공한 다음 전체 함수 또는 알고리즘의 전체 시간 복잡도를 제시하세요. 별도로 명시되지 않는 한, 사용된 내장 함수나 연산의 시간 복잡도는 O(1)로 가정하세요.

User

def 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-6",
    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)

Was this page helpful?