какова эффективность этого алгоритма

Question

Что такое большое значение O для следующего алгоритма?Почему это значение?

algorithm A (val array <ptr to int>)
     1 n = 0
     2 loop ( n < array size ) 
    1 min = n;
    2 m = n;
    3 loop ( m < array size)
      1 if (array[m] < array[min])
            1  min = m;
    4 swap(array[min],array[n]);
     3 n = n + 1

Я ответил O (n ^ 2) Я прав?Что касается того, как я пришел к этому выводу, внутренние циклы выполняются n раз, где n = размер массива, а внешний цикл выполняется n раз, где n - размер массива n * n = n ^ 2

Answer 1

Это так называемая сортировка выбора , и действительно она имеет сложность O (n ² ).

Answer 2

Да! Вы правы!

Это алгоритм сортировки выбора. Это Θ (n ^ 2), чтобы быть более точным.

Редактировать: Почему это значение?

Вы берете первый элемент. Сравните его со всеми другими элементами, чтобы найти минимум в массиве и поместить его на первое место. Итерации: n. Вы берете второй элемент. Сравните его с остальной частью массива и найдите минимум в этой части (второй минимум во всем массиве) и поместите его на второе место. Итерации: n-1. Продолжая таким образом для последнего элемента, итерации: 1.

Всего = n + n-1 + ... +1 = n (n + 1) / 2. Это O (n ^ 2).