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

Question

[eatmypants]

Есть функция с вычислением числа Фибоначчи рекурсией.

int fib(n) {
 if (n<= 2) return 1
 else return fib(n-1) + fib(n-2);
}

Нужно вычислить примерное время исполнения этой функции, если к примеру n = 100.

Comments

[Lynn «Кофеман»]

Во-первых, функция неправильная.
Во-вторых, что значит «время выполнения»? В чём вы его измеряете?

[eatmypants]

@Lynn Фукнцию поправил. Время выполнения в миллисекундах, секундах. Есть еще какие-то варианты?

[Lynn «Кофеман»]

Всё равно неправильная.

Конечно, время выполнения на калькуляторе и 64-ядерном серверном процессоре будет отличаться на порядки.

Обычно, всё-таки, считают вычислительную сложность.
ru.wikibooks.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%...

[eatmypants]

@Lynn подскажите в чем заключается неправильность функции?
Мне нужно вычислить в миллисекундах, секундах и т.д. именно на определенной машине и не важно калькулятор это или 64-ядерный серверный процессор.

[Lynn «Кофеман»]

У вас fib(2)=1, а должно быть 2.
Для конкретной машины нужно смотреть в какие процессорые инструкции превратится этот код. В общем вопрос какой-то бессмысленный.

[eatmypants]

@Lynn fib(0) = 0 , fib(1) = 1, fib(2) = 1 fib(3) = 2 и так далее. Не вижу ошибки. Проверьтесь:
php.bubble.ro/fibonacci
https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D...

Если вы не видите в этом смысла, не надо пожалуйста утверждать о бессмысленности вопроса.

[eatmypants]

Ошибка этого алгоритма в том, что даст 1 даже при 0 и при отрицательных числах, но это никак не влияет на поставленный вопрос.

[Lynn «Кофеман»]

Ну вы тогда определитесь, сейчас у вас fib(0) = 1, а не ноль.

Хорошо, задача не бессмысленна. Она просто некорректна.

Если очень хочется, то нужно сначала скомпилировать этот алгоритм, посмотреть что там получится в ассемблере, и посчитать количество тактов выполнения на каждую инструкцию…

Answer 1

[GavriKos]

Время без прямого исполнения - по сути никак. Только сложность. Можете конечно перевести ее в ассемблер, посчитать количество операций, принять что за 1 такт выполняется 1 операция (что тоже является очень грубым допущением) и дальше зная частоту процессора получить время. Но это все будет очень приблизительно. И на практике время выполнения функции будет всегда больше, причем насколько - зависит от множества параметров. Не забудьте еще разные оптимизации, другие более приоритетные вещи в ОС и процессах и т.д.

Comments

[eatmypants]

Возможно ли приблизительно как-то вычислить время выполнения без тактов?

[GavriKos]

Без тактов - нет. При фиксированной частоте процессора такт выполняется за постоянное время. И в то же время за такт условно выполняется одна процессорная операция. Другого мерила нет.

[eatmypants]

@GavriKos спасибо

Answer 2

[DancingOnWater]

Время - никак: неизвестно на какой машине, неизвестно на какой ОС, неизвестно на каком языке.