算法设计与分析考研题库.pdfVIP

算法设计与分析考研题库

第一节

1.问题描述：给定一个数组，计算数组中的逆序对数量。逆序对是

指数组中两个元素i和j，如果ij但是a[i]a[j]，则称它们为一个逆

序对。

答案和解析：使用分治算法可以在O(nlogn)的时间复杂度内解决该

问题。具体算法如下：

首先，将数组分成两半，分别求出两个子数组中的逆序对数量。-

然后，将两个子数组进行合并，合并的过程中统计逆序对的数量。-

最后，返回子数组的逆序对数量之和即可。-

代码实现如下：

```python

defmerge_sort(arr):

iflen(arr)=1:

returnarr,0

mid=len(arr)//2

left,count_left=merge_sort(arr[:mid])

right,count_right=merge_sort(arr[mid:])

merged,count_merge=merge(left,right)

returnmerged,count_left+count_right+count_merge

defmerge(left,right):

merged=[]

count=0

i,j=0,0

whileilen(left)andjlen(right):

ifleft[i]=right[j]:

merged.append(left[i])

i+=1

else:

merged.append(right[j])

count+=len(left)-i

j+=1

merged+=left[i:]

merged+=right[j:]

returnmerged,count

#调用示例

arr=[7,5,6,4]

result,count=merge_sort(arr)

dist[i][i]=0

foruintopo_order:

forvinrange(n):

ifdist[u][v]!=sys.maxsize:

forwinrange(n):

ifdist[v][w]dist[u][v]+graph[v][w]:

dist[v][w]=dist[u][v]+graph[v][w]

returndist

deftopological_sort(graph,n):

in_degree=[0]*n

zero_in_degree=[]

topo_order=[]

foriinrange(n):

forjinrange(n):

ifgraph[i][j]!=sys.maxsize:

in_degree[j]+=1

foriinrange(n):

ifin_degree[i]==0:

zero_in_degree.append(i)

whilezero_in_degree:

u=zero_in_degree.pop(0)

topo_order.append(u)

forvinrange(n