Презентация, доклад Язык программирования c#

составной оператор

блок

Линейный поиск. Элементы проверяются последовательно, по одному, до тех пор, пока нужный элемент не будет найден. Для массива из N элементов требуется, в среднем, (N+1)/2 сравнений (вычислительная сложность Оср(N)). Легко программиру-ется, подходит для коротких массивов.   Двоичный (бинарный) поиск. Применим, если массив заранее отсортирован (по возрастанию ключей). Ключ поиска сравнивается с ключом среднего элемента в массиве. Если значение ключа поиска больше, то та же самая операция повторяется для второй поло-вины массива, если меньше - то для первой. Операция повторяется до нахож-дения нужного элемента. На каждом шаге диапазон элементов в поиске умень-шается вдвое. Требуется, в среднем, (log2N+1)/2 сравнений (выч. сложность Оср(log2N)). Применяется для поиска (многократного) в больших массивах.

Критерии оценки метода сортировки: - количество необходимых операций сравнения в зависимости от числа элементов N, вычислительная сложность алгоритма характеризуется с помощью О-функции, аргументом которой является другая функция от N; - эффективность использования памяти

где S(N) - объем памяти, занимаемый элементами данных до сортировки, ΔS(N) - объем дополнительной памяти, требуемой в процессе сортировки.

1

N

2

N-1

3

N-2

4

N-3

5

N-4

Требуется, в среднем, N(N+1)/2 срав-нений (выч. сложность O(N2), не зави-сит от начальной упорядоченности). Дополнительная память не нужна.

ПОИСК НОМЕРА МИНИМАЛЬНОГО ЭЛЕМЕНТА

ПЕРЕСТАНОВКА МИНИМАЛЬНОГО ЭЛЕМЕНТА С ДРУГИМ

N

K

1

N-1

K

2

N-2

K

3

N-3

K

4

Вычислительная сложность данного метода сильно зависит от исходного расположения элементов. Минимальное значение числа сравнений – N-1 в полностью отсортированном массиве, максимальное – (N2-N)/2 при начальной сортировке в обратном порядке. Средняя вычислительная сложность Оср(N2). Доп. память не требуется.

+

ВВОД N, A(N)

A(K) ≤ A(K+1)

Q := A(K),
A(K) := A(K+1)
A(K+1) := Q

K := K + 1

K ≤ N

НАЧАЛО

B := 0

K := 1

B := B + 1

B = 0

ВЫВОД
А(1..n)

КОНЕЦ

+

a[i, j] = rnd.Next(100);
Console.Write(" ");
Console.Write(a[i, j]);
}
Console.WriteLine();
}
int summ = 0; // обнуляем сумму
// суммируются элементы на главной диагонали
if (m > n)
for (int i = 0; i < n; i++) summ += a[i, i];
else
for (int i = 0; i < m; i++) summ += a[i, i];
Console.Write("summ=");
Console.WriteLine(summ);
Console.ReadLine();
}