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

Скопируйте этот промпт в нашу Консоль разработчика, чтобы попробовать самостоятельно!

​

Пример вывода

Чтобы проанализировать временную сложность данной функции 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 запрос

Примечание: Claude 3 Opus скоро появится в Bedrock API.

import anthropic

client = anthropic.Anthropic(
    # по умолчанию используется 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)