Есть ли какие-либо инструменты, которые могут определить, выполняют анализ кода для Большой-O сложности?

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

Итак, я смог решить эту проблему, написав рекурсивную функцию следующим образом:

            function findParentsParent($result,$category) {
            global $subs;
            foreach ($result as $row) {
                if ($row['childName'] == $category['name']) {
                    $subs[] = $category['childName'];
                    findParentsParent($result,$row);
                    return array_reverse($subs);
                } elseif ($row['childName'] == $category['childName']) {
                    $subs[] = $category['childName'];
                    $subs[] = $category['name'];
                    return array_reverse($subs);
                }
            }
        }
10
задан Davy8 11 March 2009 в 19:30
поделиться

4 ответа

К сожалению, существует эта проблема, названная Проблемой остановки...

12
ответ дан 3 December 2019 в 20:06
поделиться

Нет, это не возможно, из-за проблемы остановки.

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

6
ответ дан 3 December 2019 в 20:06
поделиться

Несколько мыслей:

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

Для получения общего представления о сложности алгоритма можно всегда выполнять его на ряде случайных исходных данных и измерять потраченное время. Затем выведите кривую на печать через данные.

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

1
ответ дан 3 December 2019 в 20:06
поделиться

Никогда не замечаемый инструмент, чтобы сделать это, но мы используем профильные инструменты для получения лучшее представление, где узкие места. Это не всегда очевидно, и я был удивлен несколько раз вещами, что думал, занял много времени, на самом деле беря очень мало и наоборот. В мире.NET я использовал МУРАВЬЕВ и инструменты JetBrains.

0
ответ дан 3 December 2019 в 20:06
поделиться
Другие вопросы по тегам:

Похожие вопросы: