【算法作业】top-k和CubeSort

Uncategorized
1.7k words

问题描述

  1. 在不同应用领域，经常涉及到top-K的问题，请给出不同策略在一系列数中返回Top-K元素，并分析你的策略。

  2. 调研学习排序算法CubeSort，体会分治思想的使用。

解题思路

T1

  1. 方法一(直接排序法):

将整个数组排序，然后取前K个元素作为结果。常见的排序算法包括快速排序、归并排序等。

  • 优点： 简单直观，易于实现。
  • 缺点： 时间复杂度较高，通常为 O(nlogn)，不适用于大规模数据集。并且，如果只需要前K个元素而不需要对整个数组排序，则效率低下。
  1. 方法二(堆/优先队列):

使用堆数据结构来解决Top-K元素问题，通常是使用小根堆或大根堆。

  • 优点： 时间复杂度为 O(nlogk)，适用于大规模数据集，只需维护大小为K的堆，节省了排序整个数组的开销。
  • 缺点： 实现稍微复杂一些，需要理解堆数据结构的性质和操作。
  1. 方法三(快速选择):

这是一种改进的快速排序算法，用于查找未排序数组中的第K个最小元素。

  • 优点： 平均时间复杂度为 O(n)，在实践中通常比堆更快。
  • 缺点： 最坏情况下时间复杂度为 O(n^2)，但是通过一些优化策略可以将最坏情况的概率降低到很小。

T2

CubeSort 是一种分治排序算法，其基本思想是将待排序数组划分为多个立方体（cubes），然后分别对每个立方体进行排序，最后将这些有序的立方体合并成一个有序数组。下面是 CubeSort 算法的基本步骤：

  1. 划分立方体： 将待排序的数组划分为多个立方体，每个立方体包含固定数量的元素。立方体的数量可以根据实际情况调整，通常选择的大小与计算机内存大小和处理器缓存大小相关。

  2. 对每个立方体排序： 对每个立方体中的元素进行排序。可以选择任何一种排序算法来完成这个任务，通常选择效率较高的排序算法，比如快速排序或归并排序。

  3. 合并有序立方体： 将排序好的立方体按照一定规则合并，形成整体有序的数组。这一步可以使用归并操作来实现，将每个立方体的顶部元素依次放入一个优先队列（或堆）中，并逐步取出构建有序序列。

CubeSort 算法的时间复杂度取决于三个步骤：划分立方体、排序每个立方体以及合并有序立方体。

  1. 划分立方体： 划分立方体的时间复杂度取决于数组的大小和立方体的大小。假设数组大小为 n，立方体的大小为 m，则划分立方体的时间复杂度为 O(n/m)。

  2. 排序每个立方体： 对每个立方体进行排序的时间复杂度取决于所选的排序算法。通常情况下，可以选择效率较高的排序算法，比如快速排序或归并排序。假设所选的排序算法时间复杂度为 O(m log m)。

  3. 合并有序立方体： 合并有序立方体的时间复杂度取决于数组的大小和立方体的数量。假设立方体数量为 k，则合并有序立方体的时间复杂度为 O(n log k)。

综合考虑以上三个步骤，CubeSort 算法的总体时间复杂度为：

$$ O\left(\frac{n}{m} + m \log m + n \log k\right)$$

其中，n 表示数组的大小，m 表示立方体的大小，k 表示立方体的数量。立方体的大小和数量可以根据实际情况进行调整，以平衡算法的时间复杂度和空间复杂度。

完整代码

T1

  1. 方法一:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
using namespace std;

bool cmp(int a,int b)      
{                         
	return a > b;            
}                          
                      
int main()
{
	int n,a[100];
    cout<<"请输入数组大小：";
    cin>>n;
    cout<<"请输入数组：";
    for(int i=1;i<=n;i++){
    	int x;
    	cin>>a[i];
	}
    cout<<"请输入k：";
    int k;
    cin>>k;
	sort(a + 1, a + 1 + n, cmp);
	
	cout << "Top-k: " << a[k];

}

运行结果

1
2
3
4
请输入数组大小：5
请输入数组：2 4 1 5 3
请输入k：2
Top-k: 4
  1. 方法二:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<queue>
using namespace std;

int main() {
    // 创建一个最小堆优先队列，存储整数，找topk大的数 
    priority_queue<int, vector<int>, greater<int> > pq;

    int n;
    cout<<"请输入数组大小：";
    cin>>n;
    cout<<"请输入k：";
    int k;
    cin>>k;
    cout<<"请输入数组：";
    //这里建堆只用建k个，时间复杂度为O(klogk) 
    for(int i=1;i<=k;i++){
    	int x;
    	cin>>x;
    	pq.push(x);
	}
	// 然后只用再插入n-k个元素，时间复杂度为O((n-k)logk) 
    for(int i=k+1;i<=n;i++){
    	int x;
    	cin>>x;
    	if(x>pq.top()){
    		pq.pop();
    		pq.push(x); 	
		}
    	
	}

    // 再次访问顶部元素
    cout << "Top-k: " << pq.top();

    return 0;
}
  1. 方法三:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// 交换函数
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// 快速选择算法
int quickSelect(int arr[], int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }
    
    // 选择随机的枢纽元素
    srand(time(NULL));
    int pivotIndex = left + rand() % (right - left + 1);
    int pivot = arr[pivotIndex];
    
    // 将枢纽元素放到正确的位置上
    swap(arr[pivotIndex], arr[right]);
    int i = left;
    for (int j = left; j < right; ++j) {
        if (arr[j] > pivot) {
            swap(arr[i], arr[j]);
            ++i;
        }
    }
    swap(arr[i], arr[right]);
    
    // 根据枢纽元素的位置调整递归范围
    if (k == i) {
        return arr[i];
    } else if (k < i) {
        return quickSelect(arr, left, i - 1, k);
    } else {
        return quickSelect(arr, i + 1, right, k);
    }
}

int main() {
    int n;
    cout<<"请输入数组大小：";
    cin>>n;
    cout<<"请输入数组：";
    int arr[100]; 
    for(int i = 0; i < n; i++)
    	cin>>arr[i];
    cout<<"请输入k：";
    int k;
    cin>>k;
    int result = quickSelect(arr, 0, n - 1, k - 1); // 数组索引从0开始，所以要减去1
    cout << "top-k：" << result ;
    return 0;
}

T2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>

// 合并排序好的立方体
void mergeCubes(int arr[], int temp[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    for (int l = left; l <= right; ++l) {
        arr[l] = temp[l];
    }
}

// CubeSort 算法
void cubeSort(int arr[], int temp[], int left, int right, int cubeSize) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        cubeSort(arr, temp, left, mid, cubeSize);
        cubeSort(arr, temp, mid + 1, right, cubeSize);
        mergeCubes(arr, temp, left, mid, right);
    }
}

int main() {
    int arr[] = {3, 2, 1, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int cubeSize = 2; // 设置立方体大小为2
    int* temp = new int[n];
    cubeSort(arr, temp, 0, n - 1, cubeSize);

    std::cout << "排序后的数组: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    delete[] temp;

    return 0;
}