Метод упрощения экземпляра в технике Transform and Conquer

Упрощение экземпляра — это один из приемов Transform and Conquer. Чтобы понять упрощение экземпляра, сначала давайте разберемся, что такое преобразование и завоевание.

Transform and Conquer — это метод , основная идея которого состоит в том, чтобы преобразовать проблему в несколько более простых или похожих версий с помощью некоторой процедуры, а затем решить эти более простые или более простые версии и объединить эти версии, чтобы получить решение фактической. Конструкция состоит из двух частей:

• Первый этап включает преобразование/разбивку сложной проблемы на другие задачи, более простые, чем исходная.
• Второй этап включает в себя решение более простых задач, и после того, как проблема решена, решения объединяются и преобразуются обратно, чтобы получить решение исходной задачи.

Есть три способа сделать это:

1. Упрощение экземпляра : метод упрощения задачи до более удобных или простых экземпляров.
2. Изменение представления : структура данных преобразуется для более эффективного представления проблемы.
3. Сокращение проблемы : проблема может быть преобразована в более простую для решения проблему.

Пример:

Давайте лучше поймем упрощение экземпляра с помощью примера:

Consider the problem of finding a unique element in a given array. 

Подход 1: Чтобы решить эту проблему, можно сравнить каждый элемент со всеми другими элементами и найти уникальные элементы.

Это можно записать следующим образом:

• Обходим весь массив:
  • Для каждого элемента сравните его со всеми другими элементами, чтобы проверить, присутствует ли он где-либо или нет.
  • Если присутствует другой подобный элемент, то сообщить, что элемент не уникален.
  • В противном случае этот элемент уникален.

Алгоритм:

Algorithm unique_element( A[1. . . n]:
        for i=1 to n-1
                temp = A[i]
                for j = i+1 to n:
                        temp1 = A[j]
                        if(temp == temp1) then
                                print ‘element is not unique’
                        end if
                end for
        end for

Временная сложность: O(N ² ), поскольку алгоритм включает вложенные циклы.
Вспомогательное пространство: O(1)

Подход 2 (упрощение экземпляра): Вышеупомянутый подход был сложным в смысле сравнений. Это требует большого количества сравнений, которые можно сократить или преобразовать в более простую версию, как показано ниже.

• To identify the unique element, one can first apply any sorting technique and sort all the elements. This step is called presorting. 
• The advantage of presorting here is that for further steps, only the adjacent elements will have to be checked, instead of looking for the element in the entire array.

This is the simplification of instance where there is lesser comparison for a single element.

Подход заключается в следующем:

• Отсортируйте массив.
• Пройдитесь по массиву:
  • Для каждого элемента проверьте , совпадает ли он с соседними элементами или нет.
  • Если этот элемент один и тот же, то это не уникальный элемент.
  • В противном случае отметьте это как уникальный элемент.

Алгоритм:

Algorithm unique_element(A[1. . . n]):
        Sort (A[])
        for i = 1 to n – 1 
                temp = A[i]
                temp1 = A[i + 1]
                if(temp == temp1) then
                        print ‘element is not unique’
                end if
       end for

Анализ сложности:

• Алгоритм быстрой сортировки типа сортировки занимает O(N * logN) времени.
• Сканирование соседнего элемента для проверки уникальности требует не более (N-1) сравнений, т.е. O(N) времени.
• Следовательно, временная сложность алгоритма представляет собой сумму этих двух шагов.
• Асимптотически временная сложность равна максимуму {O(N), O(N * logN)} = O(N * logN) .

Временная сложность: O(N * logN)
Вспомогательное пространство: O(1)

Таким образом, эффективность алгоритма определяется качеством используемого алгоритма сортировки. Несмотря на то, что с точки зрения временной сложности выигрыш невелик, преимущество этого алгоритма заключается в удобстве проверки только соседних элементов.

Преимущества: преимущества метода упрощения экземпляра перечислены ниже:

• Упрощение экземпляра полезно для упрощения операций с массивами и матрицами .
• Он используется для упрощения решения экземпляра. Это своего рода разбивка сложной задачи на более простые подзадачи.
• Упрощение экземпляра также помогает в сложных манипуляциях с данными, чтобы разбить сложные данные на более простую архитектуру, упрощающую обработку данных.
• Предварительная сортировка — распространенный пример упрощения экземпляра. Предварительная сортировка, как следует из названия, опережает время. Это также форма предварительной обработки, которая представляет собой манипулирование данными для ускорения алгоритма.