【算法分析与设计】研究生第二次算法作业：基于分治策略的有序数组中位数查找与逆序对计数 latex源码和pdf

pdf：【免费】【算法分析与设计】基于分治策略的有序数组中位数查找与逆序对计数：高效算法设计及复杂度分析文档的主要内容资源-CSDN下载

\documentclass[12pt,a4paper]{article}
\usepackage{geometry}
\geometry{left=2.5cm,right=2.5cm,top=2.0cm,bottom=2.5cm}
\usepackage[english]{babel}
\usepackage{amsmath,amsthm}
\usepackage{amsfonts}
\usepackage{algorithmicx}\usepackage{algpseudocode}
\usepackage{fancyhdr}
\usepackage{ctex}
\usepackage{array}
\usepackage{listings}
\usepackage{color}
\usepackage{graphicx}
\usepackage{algorithm} 
\usepackage{algpseudocode}

\begin{document}

\title{\heiti《算法分析与设计》第二次作业}  % ctex已集成黑体

\date{} 

\maketitle

\section*{题目1：寻找两个有序数组的中位数}
设数组 $X[0..n-1]$ 和 $Y[0..n-1]$ 均为升序排列，各包含$n$个元素。要求设计时间复杂度为$O(\log n)$的分治算法，找出合并后$2n$个元素的中位数（当元素个数为偶数时取中间两个数的平均值），并证明算法的时间复杂度。

\subsection*{算法设计与分析}
\paragraph{问题转化} 合并后数组长度为$2n$，中位数等价于：
$$
\text{Median} = \frac{\text{第}n\text{小元素} + \text{第}(n+1)\text{小元素}}{2}
$$

\paragraph{分治策略} 通过递归排除无关元素实现对数时间复杂度：
\begin{enumerate}
    \item \textbf{递归基准}：
    \begin{itemize}
        \item 若某数组为空，直接取另一数组第$k$元素
        \item 当$k=1$时，返回两数组首元素较小值
    \end{itemize}
    
    \item \textbf{元素比较}：
    \begin{itemize}
        \item 取两数组前$\lfloor k/2 \rfloor$个元素（不超过数组长度）
        \item 比较临界值$X[i-1]$与$Y[j-1]$
    \end{itemize}
    
    \item \textbf{范围排除}：
    \begin{itemize}
        \item 当$X[i-1] < Y[j-1]$时，排除$X$前$i$个元素
        \item 否则排除$Y$前$j$个元素
    \end{itemize}
\end{enumerate}

\subsection*{算法伪代码}
\begin{algorithm}[H]
\caption{寻找第k小元素}
\begin{algorithmic}[1]
\Function{FindKth}{$X$, $x\_len$, $Y$, $y\_len$, $k$}
    \If{$x\_len = 0$}
        \State \Return $Y[k-1]$
    \EndIf
    \If{$y\_len = 0$}
        \State \Return $X[k-1]$
    \EndIf
    \If{$k = 1$}
        \State \Return $\min(X[0], Y[0])$
    \EndIf
    
    \State $i \gets \min(\lfloor k/2 \rfloor, x\_len)$
    \State $j \gets \min(\lfloor k/2 \rfloor, y\_len)$
    
    \If{$X[i-1] < Y[j-1]$}
        \State \Return \Call{FindKth}{$X+i$, $x\_len-i$, $Y$, $y\_len$, $k-i$}
    \Else
        \State \Return \Call{FindKth}{$X$, $x\_len$, $Y+j$, $y\_len-j$, $k-j$}
    \EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}
\subsection*{时间复杂度证明}
递归过程满足递推关系：
\[
T(k) = T\left(\frac{k}{2}\right) + O(1)
\]
由主定理可得时间复杂度为$O(\log k)$。对于中位数问题需执行两次$k=n$的查找，故总时间复杂度为：
\[
2 \times O(\log n) = O(\log n)
\]

\subsection*{代码实现}
\begin{enumerate}
    \item C++实现
    \begin{lstlisting}[language=C++, basicstyle=\small\ttfamily]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int find_kth(int X[], int x_len, int Y[], int y_len, int k) {
    if (x_len == 0) return Y[k-1];
    if (y_len == 0) return X[k-1];
    if (k == 1) return min(X[0], Y[0]);
    
    int i = min(k/2, x_len), j = min(k/2, y_len);
    return (X[i-1] < Y[j-1]) ?
        find_kth(X+i, x_len-i, Y, y_len, k-i) :
        find_kth(X, x_len, Y+j, y_len-j, k-j);
}

double findMedian(int X[], int Y[], int n) {
    return (find_kth(X,n,Y,n,n) + find_kth(X,n,Y,n,n+1)) / 2.0;
}
    \end{lstlisting}

    \item Python实现
    \begin{lstlisting}[language=Python, basicstyle=\small\ttfamily]
def find_kth(X, x_start, x_len, Y, y_start, y_len, k):
    if x_len == 0: return Y[y_start + k-1]
    if y_len == 0: return X[x_start + k-1]
    if k == 1: return min(X[x_start], Y[y_start])
    
    i = min(k//2, x_len)
    j = min(k//2, y_len)
    
    if X[x_start+i-1] < Y[y_start+j-1]:
        return find_kth(X, x_start+i, x_len-i, Y, y_start, y_len, k-i)
    else:
        return find_kth(X, x_start, x_len, Y, y_start+j, y_len-j, k-j)

def find_median(X, Y):
    n = len(X)
    m1 = find_kth(X,0,n, Y,0,n, n)
    m2 = find_kth(X,0,n, Y,0,n, n+1)
    return (m1 + m2) / 2
    \end{lstlisting}
\end{enumerate}
\section*{题目2：基于分治策略的逆序对计数算法及复杂度分析}
给定实数序列$A=\{a_1,a_2,...,a_N\}$，若存在下标$i<j$且$a_i>a_j$，则称有序对$(a_i, a_j)$为一个逆序对。本文提出基于分治算法的高效解决方案，并给出严格的时间复杂度证明。

\subsection*{算法设计与分析}
\subsubsection*{问题分析}
逆序对在序列中体现为满足$i<j$且$a_i>a_j$的有序对$(a_i,a_j)$。采用分治法的核心思想是将原问题分解为三个子问题：
\begin{itemize}
    \item 左半部分$A_L$内部的逆序对数目
    \item 右半部分$A_R$内部的逆序对数目
    \item 跨越$A_L$和$A_R$的逆序对数目
\end{itemize}

\subsubsection*{分治策略}
\begin{enumerate}
    \item \textbf{分解（Divide）}：将当前序列$A[p..r]$均分为两个子序列
    $$
    A_L = A[p..\lfloor (p+r)/2 \rfloor], \quad 
    A_R = A[\lfloor (p+r)/2 \rfloor+1..r]
    $$
    
    \item \textbf{解决（Conquer）}：递归求解子问题
    $$
    Inv_L = \text{Count}(A_L), \quad 
    Inv_R = \text{Count}(A_R)
    $$
    
    \item \textbf{合并（Combine）}：在归并有序子序列时统计跨子序列逆序对
\end{enumerate}

\subsubsection*{关键步骤}
归并过程中的逆序对计数策略：
\begin{itemize}
    \item 当右子数组元素$a_j$被选入合并数组时
    \item 左子数组剩余元素数量$count = |A_L| - i$ 
    \item 此时$a_j$贡献的逆序对数为$count$
    \item 即：$\forall k \in [i, |A_L|), a_k > a_j$
\end{itemize}

\subsubsection*{形式化伪代码描述}
\begin{algorithm}[H]
\caption{逆序对计数算法}
\begin{algorithmic}[1]
\Function{CountInversions}{$A[0..n-1]$}
    \If{$n \leq 1$}
        \State \Return $(0, A)$
    \EndIf
    \State $mid \gets \lfloor n/2 \rfloor$
    \State $(left\_inv, L) \gets \text{CountInversions}(A[0..mid-1])$
    \State $(right\_inv, R) \gets \text{CountInversions}(A[mid..n-1])$
    \State $(cross\_inv, A') \gets \text{MergeCount}(L, R)$
    \State \Return $(left\_inv + right\_inv + cross\_inv, A')$
\EndFunction

\Function{MergeCount}{$L[0..p-1], R[0..q-1]$}
    \State $i \gets 0, j \gets 0, k \gets 0, inv \gets 0$
    \State Initialize $merged[0..p+q-1]$
    \While{$i < p$ \textbf{and} $j < q$}
        \If{$L[i] \leq R[j]$}
            \State $merged[k++] \gets L[i++]$
        \Else
            \State $merged[k++] \gets R[j++]$
            \State $inv \gets inv + (p - i)$  
        \EndIf
    \EndWhile
    \State Copy remaining elements
    \State \Return $(inv, merged)$
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection*{时间复杂度分析}
设$T(n)$表示处理长度为$n$的数组所需时间，可得递推关系：
$$
T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)
$$
根据主定理（Master Theorem）：
\begin{itemize}
    \item $a = 2$, $b = 2$, $f(n) = \Theta(n)$
    \item 满足情况2：$f(n) = \Theta(n^{\log_b a})$
    \item 得时间复杂度为$\Theta(n \log n)$
\end{itemize}

\subsection*{代码实现}
\begin{enumerate}
    \item \textbf{C++实现}
    \begin{lstlisting}[language=C++, basicstyle=\scriptsize\ttfamily]
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

using namespace std;

int mergeAndCount(vector<int>& arr, const vector<int>& left, const vector<int>& right) {
    int i = 0, j = 0, k = 0, inv_count = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
            inv_count += (left.size() - i);
        }
    }
    while (i < left.size()) arr[k++] = left[i++];
    while (j < right.size()) arr[k++] = right[j++];
    return inv_count;
}

int countInversions(vector<int>& arr) {
    if (arr.size() <= 1) return 0;
    int mid = arr.size() / 2;
    vector<int> left(arr.begin(), arr.begin() + mid);
    vector<int> right(arr.begin() + mid, arr.end());
    int inv = countInversions(left) + countInversions(right);
    vector<int> merged(arr.size());
    inv += mergeAndCount(merged, left, right);
    arr = merged;
    return inv;
}

int main() {
    int n;
    cout << "请输入n的值：";
    cin >> n;
    vector<int> arr;
    if (n == -1) {
        srand(time(0));
        int length = rand() % 6 + 5;
        arr.resize(length);
        for (int& num : arr) num = rand() % 100 + 1;
        cout << "随机生成的数组：";
        for (int num : arr) cout << num << " ";
        cout << endl;
    } else {
        arr.resize(n);
        cout << "请输入数组元素（空格分隔）：";
        for (int i = 0; i < n; ++i) cin >> arr[i];
    }
    vector<int> temp = arr;
    cout << "逆序对数目：" << countInversions(temp) << endl;
    return 0;
}
    \end{lstlisting}
    
    \item \textbf{Python实现}
    \begin{lstlisting}[language=Python, basicstyle=\scriptsize\ttfamily]
from typing import Tuple, List

def count_inversions(arr):
    if len(arr) <= 1:
        return 0, arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    left_inv, left_sorted = count_inversions(left)
    right_inv, right_sorted = count_inversions(right)
    merge_inv, merged = merge(left_sorted, right_sorted)
    total = left_inv + right_inv + merge_inv
    return total, merged

def merge(left, right):
    merged = []
    i = j = inv_count = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            inv_count += len(left) - i
            j += 1
    merged += left[i:]
    merged += right[j:]
    return inv_count, merged

n = int(input("请输入n的值："))
if n == -1:
    import random
    length = random.randint(5, 10)
    arr = [random.randint(1, 100) for _ in range(length)]
    print("随机生成的数组：", arr)
else:
    arr = list(map(int, input("请输入数组元素，空格分隔：").split()))
    if len(arr) != n:
        print("输入长度不匹配！")
        exit()
total, _ = count_inversions(arr)
print("逆序对数目：", total)
    \end{lstlisting}
\end{enumerate}
\end{document}