ds4

24.10.10 hw4

1

C

C
B
CB

2

int temp[N*M],s[N*M];
void sort(int l,int r){
	if(l==r) return;
	int mid=(l+r)/2;
	sort(l,mid);
	sort(mid+1,r);
	int i=l,j=mid+1,p=0;
	while(i<=mid&&j<=r){
		if(a[i]>a[j]) temp[++p]=a[j],j++;
		else temp[++p]=a[i],i++;
	}
    while(i<=mid) temp[++p]=a[i],i++;
    while(j<=r) temp[++p]=a[i],j++;
	p=0;
	for(int i=l;i<=r;i++) s[i]=temp[++p];
}
void check(int (*a)[N]){
    int p=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            s[++p]=a[i][j];
        }
    }
    sort(1,m*n);
    for(int i=1;i<m*n;i++){
        if(s[i]==s[i+1]){
            puts("no");
            return;
        }
    }
    puts("yes");
}

复杂度分析：在排序中，每次递归排序的区间长度减半，共递归 \(O(\log nm)\) 层，同样层数的递归中时间复杂度总和为 \(O(nm)\)，因此排序复杂度为 \(O(nm\log nm)\)。
在判断中，遍历所有元素一遍，复杂度 \(O(nm)\)。
因此，总复杂度为 \(O(nm\log nm)\)。