Что это значит «Обнаруженная сложность времени: O (Y-X)»?

Question

Я занимаюсь некоторыми методами кодирования Codility, и в результате я получил «Обнаруженная сложность времени: O (YX)».Я не понимаю, что это на самом деле означает.Это из-за моего паршивого и постоянного зацикливания?Как улучшить или улучшить производительность, чтобы избавиться от этой низкой производительности?

public static int Solution(int startPoint, int endPoint, int frogJumpPowerDistance)
{
            int jumpCount = 0;

            // AIM: return the number of jumps to reach endPoint

            // CHECK: no jump needed.
            if (startPoint == endPoint) return jumpCount;

            int distanceReach = startPoint + frogJumpPowerDistance;
            jumpCount++;
            if (distanceReach < endPoint)
            {
                //enter checking loop
                do
                {
                    distanceReach += frogJumpPowerDistance;
                    jumpCount++;
                }
                while (distanceReach < endPoint);
            }

            return jumpCount;
}

Я ожидаю, что не получит ошибку Timeout.Но я понял.

Я не уверен, как улучшить свои коды для решения ошибки тайм-аута.

Для входа (5, 1000000000, 2) решение превысило ограничение по времени.

Для вашей информации,

1. Все входы находятся в пределах диапазона[1 ... 1 000 000 000].

2. начальная точка меньше или равна конечной точке.

Answer 1

Я думаю, что «Обнаруженная сложность времени: O (Y-X)» означает, что ваш код требует больше времени для запуска, когда начало и конец находятся дальше друг от друга. В частности, время, необходимое для запуска вашего кода, увеличивается линейно относительно разницы между началом и концом. Обратите внимание, что я предполагаю, что Y - это конец, а X - это начало.

Тебе не нужен цикл здесь. Вы можете просто посчитать, сколько вам нужно прыжков, и сделать это за постоянное время O (1).

Сначала вы рассчитываете расстояние, которое вы должны прыгнуть, вычисляя разницу между началом и концом:

int distance = endPoint - startPoint;

Затем разделите расстояние на мощность прыжка:

int jumps = distance / frogJumpPowerDistance;

Если distance делится на frogJumpPowerDistance, то мы можем просто вернуть jumps. В противном случае у нас все еще остается некоторое расстояние после того, как мы прыгнули jumps раз (это целочисленное деление!). Поэтому нам нужен еще один прыжок, чтобы завершить его.

if (distance % frogJumpPowerDistance == 0) {
   return jumps;
} else {
   return jumps + 1;
}

EDIT:

Как предложил Якобский в комментариях, это также можно сделать всего одним делением, например:

return (distance - 1) / frogJumpPowerDistance + 1;

Answer 2

Я получил это "Обнаруженная сложность времени: O (YX)".

Теоретически вы линейно движетесь к конечной точке от начальной точки с определенным значением скачка, но важноСмысл в том, что происходит, если вам нужно достичь 1 млрд. всего за 2 шага за раз?

Набор задач, на который вы ссылались, является арифметической прогрессией, где:

Begin Value = 5,End Value = 10^9 (1 billion), Common Difference = 2

Используя простую формулу арифметической прогрессии, чтобы узнать количество элементов ( Общее количество прыжков ) в этой прогрессии, оно будет:

a(n) = a(0) + (n-1)*(Common Difference), здесь (Common Difference) будет вашим значением прыжка frogJumpPowerDistance, простая подстановка предложит значение в виде:

10^9 = 5 + (n-1) * 2, n будет приблизительно 500 миллионов игнорирование незначительного сложения и вычитания

Что это значит?

При вычислении нотации Big O для сложности времени, пока мы будем использовать логику циклического анализа, она будет примерноO (N) и значение N слишком высоко, как рассчитываетсяс рейтингом выше 500 млн.

Каковы ваши варианты, чтобы сделать это быстрее при той же O(N) сложности

• Увеличьте значение frogJumpPowerDistance, предположим, высделайте это 1000, N (количество прыжков) будет приблизительно 1 миллион, огромное сокращение по сравнению с последним, и так далее и так далее

Поэтому идея заключается либо в существенном улучшении frogJumpPowerDistance,чтобы сделать его более совершенным алгоритмом или, если он хорошо подходит, использовать одну из предложенных формул, вы можете использовать формулу арифметической прогрессии.

В большинстве случаев мы не можем использовать прямую формулу для решения набора математических задач, еезацикливание структуры данных, такой как List по O(N) времени или может быть O(LogN), если вы можете уменьшить на 1/2 на каждом этапе, предполагая логарифм до основания 2, но суть заключается в уменьшении значенияN, и увеличение Common difference или Jump value на значительную величину, что делает алгоритм быстрее.