Как определить сложность функции алгоритма?

Question

Как вы узнаете, занимает ли функция алгоритма линейное / постоянное / логарифмическое время для конкретной операции?это зависит от циклов процессора?

Answer 1

Есть три способа сделать это (по крайней мере).

1. Посмотрите алгоритм в сети и посмотрите, что он говорит о его временной сложности.

2. Изучите алгоритм самостоятельно, чтобы взглянуть на такие вещи, как вложенные циклы и условия рекурсии, а также на частоту выполнения каждого цикла или каждой рекурсии в зависимости от размера ввода.Расширением этого является строгий математический анализ.

3. Эксперимент.Измените входную переменную и посмотрите, сколько времени это займет в зависимости от этого.Вычислите уравнение, которое дает вам указанное время выполнения, на основе переменной (одновременное решение уравнения является одной из возможностей здесь для функций типа O (n ^c ).

Из нихВероятно, первый вариант является самым простым для непрофессионала, так как он почти наверняка будет создан кем-то более знающим, делающим второе: -)

Answer 2

О зависимости от процессора: Ответ НЕТ - сложность времени полностью независима от процессора. Это связано с тем, что сложность показывает - как требования алгоритма к ресурсам процессора возрастают с увеличением размера входных данных алгоритма Другими словами, это функция. И функции везде одинаковы - будь то на разных машинах или на разных планетах:)

Answer 3

Сначала выполнение функции может занять некоторое время.Он также может быть совершенно нелинейным и даже бесконечным.

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

Более точную информацию вы можете получить здесь WIKI :: Теория сложности вычислений