Библиотека промптов

Оценка эффективности

Рассчитайте временную сложность функций и алгоритмов.

Скопируйте этот запрос в наш разработчик 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?