Сортировка и поиск Базис. Матрица оператора. Проблема поиска в базисе. Способы сортировки

задач при формировании базисных функций системы, а также при построении

матриц операторов в выбранном базисе
Система из трех ящиков и двух одинаковых шаров. Базис системы:







В системе всего 6 возможных состояний

шар из третьего ящика во второй:


Матрица, отражающая работу этого

устройства:

некоторый оператор в базисе, и построена матрица, соответствующая этому оператору
В

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

в том случае, если состояния, входящие в базис, пронумерованы в

соответствии с определенной схемой:







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

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






Временные затраты при

сортировке вставками составляют порядка N2 операций
Этот способ сортировки является неэкономным

и каким-либо образом отделяется от остальных, затем выбирается наименьший (наибольший)

элемент из оставшихся и т.д.:







Как и метод вставок, этот способ сортировки требует порядка N2 операций

порядку, этот процесс повторяется до тех пор, пока не будут

перебраны все возможные пары элементов:








Временные затраты при этом способе сортировки составляют порядка N2/2 операций

проводится обычная сортировка

Далее на каждом шаге выбирается минимальный элемент среди

наименьших элементов каждого блока

Весь алгоритм требует порядка N3/2 операций
Существуют алгоритмы, доводящие время сортировки до Nlog2N операций