声明：仅供留档查阅，仅用作起到提示引导性作用，仅用作学习交流，切勿直接照搬

DS作业-2-22网安物联网-20230913

作业Ch1-4: P24-P25 1.选择题

1-5 CD B B A A 6-9 C CE

第九题解析

这段代码的时间复杂度是O(n²)。这是因为外部循环会执行n次，而内部循环会执行2i次，其中i的最大值是n。因此，最坏情况下，内部循环会执行2n次。所以，总的执行次数是n(2n)，即O(n²)。这意味着，如果输入大小（即n的值）增加，那么执行时间将按平方增加。这是典型的二次时间复杂度的例子。

作业Ch1-5:

算法编程题，给出代码、测试过程和运行结果：

这个题存疑，算法思路还没看懂

将一个具有 n 个元素的数组A[n]向左循环移动k个位置，要求时间复杂度为O(n)，空间复杂度为O(1)。

答案（来自bing ai

这是一个经典的问题，可以通过三次反转数组的方法来解决。首先，我们将数组的前k个元素反转，然后将剩余的元素反转，最后将整个数组反转。这样就可以实现将数组向左循环移动k个位置。以下是具体的C++代码实现：

#include<iostream>
using namespace std;

void reverse(int A[], int start, int end) {
    while(start < end) {
        swap(A[start], A[end]);
        start++;
        end--;
    }
}

void leftRotate(int A[], int n, int k) {
    reverse(A, 0, k-1);
    reverse(A, k, n-1);
    reverse(A, 0, n-1);
}

int main() {
    int A[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(A)/sizeof(A[0]);
    int k = 2;
    
    leftRotate(A, n, k);
    
    for(int i = 0; i < n; i++) {
        cout << A[i] << " ";
    }
    
    return 0;
}

这段代码首先定义了一个reverse函数，用于反转数组中从start到end的元素。然后定义了一个leftRotate函数，用于将数组向左循环移动k个位置。在main函数中，我们创建了一个数组，并调用了leftRotate函数来进行旋转。最后，我们打印出旋转后的数组。

这个解决方案的时间复杂度为O(n)，空间复杂度为O(1)，满足了题目的要求。希望这个答案对你有所帮助！

新知识，要使其不大于最大长度可以用取模运算来解决

作业Ch1-6:

算法编程题，给出代码、测试过程和运行结果：

找出整型数组A[n]中的最大值和次最大值。

答案（来自bing ai

以下是一个C++代码片段，它可以找出整型数组A[n]中的最大值和次最大值。这个代码假设数组中至少有两个元素，并且所有元素都是唯一的。

#include<iostream>
using namespace std;

void findMaxAndSecondMax(int A[], int n) {
    int max1 = A[0], max2 = A[0];
    for(int i = 1; i < n; i++) {
        if(A[i] > max1) {
            max2 = max1;
            max1 = A[i];
        } else if(A[i] > max2) {
            max2 = A[i];
        }
    }
    cout << "最大值: " << max1 << ", 次最大值: " << max2 << endl;
}

int main() {
    int A[] = {1, 2, 3, 4, 5, 6, 7};
    int n = sizeof(A)/sizeof(A[0]);
    
    findMaxAndSecondMax(A, n);
    
    return 0;
}