프롬프트 라이브러리
효율성 추정기
함수와 알고리즘의 시간 복잡도를 계산합니다.
이 프롬프트를 우리 개발자 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) |
예시 출력
예시 출력
주어진 함수
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 요청
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-sonnet-4-5",
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)