Порядок скорости алгоритма

Вы можете преобразовать строку в массив и проверить, является ли каждый элемент строки (разделенный пробелом) цифрой, протестировав метод Integer.parseInt () для каждого элемента строки. Вот пример ниже:

public static boolean isDig(String theString) {
    String[] theStringArray = theString.split(" ");
    ArrayList<Integer> nums = new ArrayList<Integer>();
    for(int x = 0; x < theStringArray.length; x++) {
        String thisString = theStringArray[x];
        try {
            int num = Integer.parseInt(thisString);
            nums.add(num);
        }catch(NumberFormatException e) {
            continue;
        }
    }
    int total = 0;
    for(int num: nums) {
        total += num;
    }
    if(total >= 80 && total <= 95) {
        return true;
    }
    else {
        System.out.println(total);
        return false;
    }
}

Сначала мы разбиваем исходную строку на массив, основанный на пустых местах. Затем мы создаем ArrayList, который добавит к нему каждую цифру в строке. Затем мы создаем цикл for для просмотра каждой отдельной строки в массиве и устанавливаем блок try-catch. Если мы можем преобразовать цифру в int с помощью метода Integer.parseInt (), мы добавим ее в ArrayList. Если нет, мы перехватим исключение и продолжим цикл с помощью оператора continue. Как только мы вырвемся из цикла, мы можем создать переменную под названием «total» и создать еще одну для цикла, чтобы добавить каждую цифру в ArrayList к общей сумме. Если сумма больше / равна 80 и меньше / равна 95, мы вернем True, иначе вернем false. Давайте проверим код:

String digitTest = "There is a digit here: 50 and a digit here 45";
System.out.println(isDig(digitTest));

Числа 50 и 45 должны быть равны 95, и наш результат:

true
6
задан Maksym Gontar 27 September 2009 в 07:27
поделиться

7 ответов

Рекурсивные, алгоритмы делить-и-побеждать часто O (logN). Алгоритм, что циклы по делить-и-побеждать были бы O (NlogN).

7
ответ дан 8 December 2019 в 05:58
поделиться

Вот сообщение в блоге, которое могло бы помочь:

Стоимость разрушения вещей и откладывания их вместе

То сообщение объясняет "основную теорему" для работы с большими-O заказами.

7
ответ дан 8 December 2019 в 05:58
поделиться

O (LG (n)): Если Ваша проблема становится меньшей некоторой пропорцией n (часто n/2) на каждом шаге Вашего алгоритма, и каждый шаг делает постоянный объем работы. Двоичный поиск является хорошим примером, так как каждый шаг сокращает Ваш проблемный размер в половине путем выполнения постоянного объема работы (вычислите среднюю точку и сделайте одно сравнение).

Обратите внимание, что n находится на вершине той пропорции. Это не то же как Ваше сокращение размера задач 1/n на каждом шаге.:)

4
ответ дан 8 December 2019 в 05:58
поделиться

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

Править: John D. Cook сделал хорошее резюме к основной теореме, см. Ссылку его ответ.

1
ответ дан 8 December 2019 в 05:58
поделиться

Статья Wikipedia о Большой Нотации O имеет хорошую диаграмму заказов общих функций.

1
ответ дан 8 December 2019 в 05:58
поделиться

асимптотическая сложность алгоритмов важна на практике и здесь является некоторыми эмпирическими правилами, которые я использую, когда я рассматриваю мой или чужой код. Обычно практические компьютерные алгоритмы являются функциями многих переменных и нетривиальных структур данных, но позволяют нам принять (только для иллюстрации), что наш алгоритм f берет в основном единственное целое число X как его аргумент, и мы хотим найти асимптотическую сложность f с точки зрения X. Предположим, что f (0) тривиален. Затем в целом:

  • Каждый вложенный цикл от 0 до X добавляет экспоненту к X, таким образом, два цикла (один вложенный в другом) дают X ** 2 (квадратичный).
  • Если f (X) вызовы f (X-1) хвост рекурсивно, это обычно соответствует повторению, т.е. единственному внешнему циклу (O (X)).
  • Я видел стандартные программы, которые автор предназначил как повторяющиеся, но где существует оба повторение от 0.. X И хвостовая рекурсия к X-1; они приводят к квадратичному поведению (O (X ** 2))
  • Если f (X) вызовы f (X-1) дважды или больше, это приводит к экспоненциальному алгоритму, и Вы получаете O (2 ** X) от этого.
  • Если f (X) вызовы f (X/2) дважды, это соответствует мудрое сложностью единственному повторению (это - алгоритм делить-и-побеждать). (Это приводит к O (X журналов X) или O (X) в зависимости от деталей, но я понимаю, что думаю о нем как о единственном повторении так или иначе.)
  • Если f использует какую-либо заказанную структуру данных (упорядоченное множество, приоритетная "куча" и т.д.), который был правильно реализован, и алгоритм добавляет примерно X объектов к структуре данных, операции являются O (зарегистрируйтесь X). Таким образом, если постоянное количество операций структуры данных происходит в цикле, скажем, Вы добираетесь, O (X * регистрируются X).
  • Если заказанная структура данных неправильно реализована, Вы могли бы добраться, O (X) вместо O (зарегистрируйтесь X) для отдельных операций.

Некоторые особые случаи:

  • Алгоритмы, которые выращивают строки или области памяти путем добавления им, делают на многих языках, подвергаются O (X ** 2) наверху, такой как

    for (i = 0; i < X; i++) { s += "foo"; } // quadratic
    
  • Этот типичный вложенный цикл имеет также X ** 2 наверху:

    for (i = 0; i < X; i++) { for (j = 0; j < i; j++) { ... } } // quadratic
    
  • C++ контейнеры STL как станд.:: набор и станд.:: карта имеет O (зарегистрируйтесь X), издержки почти для всех операций

  • strlen (s) и другие подобные алгоритмы подсчета, когда они возвращаются X, имеют O (X) издержки
  • memcpy и т.д. приводят к O (X)
  • Существуют мудрые сложностью опасные операции, такие как стирание элемента по сравнению равенства из связанного списка, которые приводят к O (X) или хуже
  • При использовании основанных на шаблоне контейнеров удостоверьтесь, что сравнение, заказывая и т.д. операторы быстро и не имеет скрытых коэффициентов сложности
  • При использовании подсчета ссылок отбрасывание ссылки может быть худшим случаем O (X) операция при отбрасывании последней ссылки на связанный список ссылок, длина которых X
  • Копирование сложных структур данных на объектно-ориентированных языках может привести к странным асимптотическим сложностям, если стандартные программы для копирования объектов нетривиальны и например, обновляют наборы глобального объекта

Просто мои 2 цента!Надеюсь, это поможет!

1
ответ дан 8 December 2019 в 05:58
поделиться

Usually something like O(logN) comes about because the data is size N, but it is organized e.g. in a tree where the depth of the tree is logN. If the typical search involves going from the root to the leaf (in worse case) then it is easy to see that the algorithm will be O(logN).

There are no hard and fast rules - you just have to look at each case, figure out the worse case scenario, and calculate what the cost of that would be.

1
ответ дан 8 December 2019 в 05:58
поделиться
Другие вопросы по тегам:

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