Как определить время выполнения для двух методов обратной строки в нотации O ()?

Question

У меня есть два запроса, чтобы перевернуть строку.Нужно сравнить их:

public string ReverseD(string text)
{
    return new string(text.ToCharArray().Reverse().ToArray());
}

public string ReverseB(string text)
{
    char[] charArray = text.ToCharArray();
    Array.Reverse(charArray);
    return new string(charArray);
}

Как определить время выполнения этих двух алгоритмов в записи O ()?Нужно сравнить.

Answer 1

Оба являются O (n) - они оба проходят через весь массив, который является O (n).

Первый алгоритм имеет худший постоянный коэффициент , хотя, поскольку вы эффективно «буферизуете» полный массив, а затем генерируете его в обратном порядке (если Enumerable.Reverse() не оптимизирован для массивов под капотом, не Отражатель пригодится прямо сейчас). Поскольку вы буферизируете полный массив, то создаете новый массив в обратном порядке, вы можете сказать, что усилие равно 2 * N, поэтому постоянный коэффициент c = 2.

Второй алгоритм будет использовать индексы массива, поэтому вы выполняете n / 2 перестановки элементов в одном и том же массиве - все еще O (n), но постоянный коэффициент c = 0,5.

Answer 2

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

В подобных случаях действительно полезнее просто запустить оба алгоритма несколько раз и посмотреть, какой из них требуетсяменьше времени.

Скорее всего, это будет прямая версия Array.Reverse(), так как она будет интеллектуально менять элементы в массиве, тогда как метод Enumerable.Reverse() будет yield return каждый элемент в обратном порядке.Любой из них будет O (n), так как они оба манипулируют каждым из n элементов в массиве постоянное число раз.

Но, опять же, лучший способ увидеть, какой из них будет работать лучше, - это на самом деле запустить ихи см.