Время работы и память

Question

Если вы не видите код функции, но знаете, что она принимает аргументы.Можно ли найти скорость бега и память.Если так, как бы вы это сделали?Есть ли способ использовать Big O в этом случае?

Answer 1

Нет, невозможно найти ни память, ни производительность функции, просто взглянув на ее параметры. Например, та же функция

void DoSomething(int x, int y, int z);

Может быть реализовано как O (1) время и память:

void DoSomething(int x, int y, int z) { }

или как очень, очень дорогая функция, принимающая O (x * y * z):

void DoSomething(int x, int y, int z)
{
  int a = 0;
  for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
      for (int k = 0; k < z; k++) {
        a++;
      }
    }
  }
  Console.WriteLine(a);
}

и много других возможностей. Таким образом, невозможно определить, насколько дорогая функция.

Answer 2

Разрешено ли вообще запускать функцию? Несколько раз?

Я выполняю функцию с диапазоном значений параметров и измеряю время работы и (если возможно) потребление памяти для каждого запуска. Затем, предполагая, что функция принимает аргумент n, я строил бы каждую точку данных на n+1 -мерном графике и искал тренды оттуда.

Answer 3

Будучи вопросом для интервью, вы никогда не должны отвечать, как «нет, это не может быть сделано».

Что вам нужно, так это умение запускать код.Как только вы сможете запустить код, вызовите одну и ту же функцию с различными параметрами и измерьте требуемую память и время.Затем вы можете построить эти данные и получить хорошую оценку.

Также для обозначений типа big-O вы можете следовать тому же подходу и построить результаты WRT с размером набора данных.Затем попытайтесь согласовать эту кривую с известными кривыми сложности, такими как n, n ^ 2, n ^ 3, n * log (n), (n ^ 2) * log (n) и т. Д., Используя подбор по методу наименьших квадратов.

Наконец, помните, что все эти методы являются только приблизительными.

Answer 4

Прежде всего, это вопрос интервью, так что вам лучше никогда не говорить «нет».

---

Если бы я был на собеседовании, вот мой подход.

Я могу задать интервьюеру несколько вопросов, поскольку интервью должно быть интерактивным.

Поскольку я не вижу код, я полагаю, что, по крайней мере, могу запустить его несколько раз. Это будет мой первый вопрос: могу ли я его запустить? (Если я не могу запустить его, то буквально ничего не могу с этим поделать, и я сдаюсь.)

Для чего используется функция? Это может дать намек на сложность, если функция написана разумно.

Какого типа аргумент? Это какие-то примитивные типы? Попробуйте несколько их комбинаций. Являются ли некоторые из них "сложными" (например, контейнеры)? Попробуйте несколько разных комбинаций размеров. Связаны ли некоторые из них (например, один для контейнера, а другой для размера контейнера)? Некоторые тестовые прогоны могут быть сохранены. Кроме того, я надеюсь, что правовые диапазоны аргументов приведены, поэтому я не буду тратить время на незаконные догадки. Наконец, может помочь проверка некоторых предельных случаев.

Answer 5

Можете ли вы запустить функцию с кодом? как то так:

start = clock();
//call the function;
end = clock();
time = end-start;

Answer 6

нет, вы не можете, это решило бы проблему остановки , так как код мог бы бесконечно работать O (бесконечность).таким образом, решение этой проблемы также решает HP, что, конечно, оказалось невозможным.