Алгоритм поиска наибольшего элемента в списке из N элементов:
Поэтому чтобы не получить ложное представление об алгоритме, нужно рассматривать различные возможные множества входных значений.
Различные входные множества разбиваются на классы в зависимости от поведения алгоритма на каждом множестве.
Например, число различных расстановок 10 различных чисел в списке есть 10! = 3 628 800.
Имеется 362 880 входных множеств, у которых первое число является наибольшим; их все можно поместить в один класс.
Множеств, в которых наибольшее по величине число стоит на втором месте, 362 880. Их можно отнести к другому классу.
Видно, как будет меняться число присваиваний при изменении положения наибольшего числа от 1 до N. Все входные множества нужно разбить на N разных классов по числу сделанных присваиваний. Нужно знать количество классов и объем работы на каждом множестве класса.
Такое разбиение основывается на местоположении наибольшего значения.
Для алгоритма поиска наибольшего и наименьшего значения разбиение могло бы основываться на том, где располагаются наибольшее и наименьшее значения. В таком разбиении 90 классов.
Если классы выбраны правильно, то на всех множествах входных данных одного класса алгоритм производит одинаковое количество операций, а на множествах из другого класса это количество операций скорее всего будет другим.
#import <Foundation/Foundation.h> #define N 10 int main(int argc, const char * argv[]) { @autoreleasepool { int list[N] = {5, 6, 8, 9, 4, 2, 3, 55, 23, 1}; int largest = list[0]; // largest = list [1] for (int i = 1; i < N; i++) // for i = 2 to N do { if (list[i] > largest) // if (list [i] > largest) then { largest = list[i]; // largest = list[i] } // end if } // end for NSLog(@"%i", largest); } return 0; }
- Если список упорядочен в порядке убывания, то перед началом цикла будет сделано одно присваивание, а в теле цикла присваиваний не будет.
- Если список упорядочен по возрастанию, то всего будет сделано N присваиваний (одно перед началом и N - 1 в цикле).
Поэтому чтобы не получить ложное представление об алгоритме, нужно рассматривать различные возможные множества входных значений.
Различные входные множества разбиваются на классы в зависимости от поведения алгоритма на каждом множестве.
Например, число различных расстановок 10 различных чисел в списке есть 10! = 3 628 800.
Имеется 362 880 входных множеств, у которых первое число является наибольшим; их все можно поместить в один класс.
Множеств, в которых наибольшее по величине число стоит на втором месте, 362 880. Их можно отнести к другому классу.
Видно, как будет меняться число присваиваний при изменении положения наибольшего числа от 1 до N. Все входные множества нужно разбить на N разных классов по числу сделанных присваиваний. Нужно знать количество классов и объем работы на каждом множестве класса.
Такое разбиение основывается на местоположении наибольшего значения.
Для алгоритма поиска наибольшего и наименьшего значения разбиение могло бы основываться на том, где располагаются наибольшее и наименьшее значения. В таком разбиении 90 классов.
Если классы выбраны правильно, то на всех множествах входных данных одного класса алгоритм производит одинаковое количество операций, а на множествах из другого класса это количество операций скорее всего будет другим.
