Инструмент для расчета сложности времени Java-кода? - PullRequest
Новая
       5

Инструмент для расчета сложности времени Java-кода?

12 голосов
/ 31 марта 2012

У меня есть вопрос, касающийся сложности времени (большая буква О) для программного обеспечения Java.Есть ли способ быстро рассчитать или протестировать его (или любой сайт, который мог бы рассчитать его для меня, будет приветствоваться).Например, я хотел бы проверить его на наличие следующего фрагмента кода и, возможно, улучшить его: 

int dcount = 24423567;
        int a = 0;
        if (dcount == 0){
            a = 1;
        }

        String ds = Integer.toString(dcount);
        String[] sa = ds.split("(?<=.)");
        HashSet hs = new HashSet();
        Collections.addAll(hs, sa);
        a = hs.size();
        if (dcount < 0)
            a--;

        System.out.println(a);

Ответы [ 2 ]

14 голосов
/ 31 марта 2012

Как указывало @emory, доказуемо невозможно автоматически определить сложность произвольного фрагмента кода во времени больших чисел (доказательство - сокращение от проблемы остановки ). Однако существуют инструменты, которые могут попытаться измерить сложность фрагмента кода эмпирически, запустив его на нескольких различных входных данных. Один из таких инструментов описан в статье «Измерение эмпирической вычислительной сложности» Голдсмитом, Айкеном и Уилкерсоном. Он работает, пытаясь сделать регрессию во время выполнения программы в зависимости от ее входного размера. Инструмент под названием trend-prof доступен онлайн.

Надеюсь, это поможет!

1 голос
/ 31 марта 2012

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

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

Следующий метод выполняется за время O (n) (n = количество цифр на входе) и в постоянном пространстве: 

int distinctDigits(int num) {
  if (num == 0) {
    return 1;
  }

  boolean[] digits = new boolean[10];

  while (num > 0) {
    digits[num % 10] = true;
    num /= 10;
  }

  int count = 0;
  for (boolean digit : digits) {
    if (digit) {
      count++;
    }
  }

  return count;
}

Выполнение этой работы для отрицательных чисел оставляется в качестве упражнения длячитатель;)

...