Алгоритмы и анализ сложности. Простые алгоритмы поиска и сортировки
Задача и результаты поиска в массиве Задача поиска: Задан массив A из n элементов и некоторое значение p (поисковое). Требуется найти такой номер i, что A[i]=p. Возможные результаты поиска: существует единственный элемент с номером i, для которого A[i]=p A[i]≠p при любых i=0,1,...,n-1 существует несколько элементов с номерами i1,i2,... таких, что A[i1]=p,A[i2]=p,... Поиск одного элемента в неупорядоченном массиве int find_int(int *A, int n, int p) { for (int i = 0; i < n; i++) if (A[i] == p) return i; return -1; } int find_double(double *A, int n, double p, double eps) { for (int i = 0; i < n; i++) if (abs(A[i]–p) < eps) return i; return -1; } Трудоемкость в наилучшем: T(n) = O(1) Трудоемкость в наихудшем: T(n) = O(n)