（1）试说明怎样的计算步骤我们称之为“元运算”？符合怎样条件的元运算，我们 称之为“基本运算”？试举例说明两种算法中的基本运算。 （2）关于算法的空间复杂性，试给出算法所使用空间的定义。算法的空间复杂性和 时间复杂性之间存在怎样的关系？ （3）试分别给出确定性算法和不确定性算法的定义。何为不确定多项式类型的算 法？ 二、设计一个时间复杂性为 O(n)的算法对 n 个实数组成的数组进行重新排列，使得 其中所有的负元素都位于正元素之前。你设计的算法的空间复杂度是多少？ 三、使用随机算法求解 sin(x)/x 在区间[1,2]上的定积分值∫ 𝐬𝐢𝐧 (𝒙) 𝒙 𝒅𝒙 𝟏 𝟐 。假设已有随机 数发生器 random()可以生成 0 到 1 之间的随机实数。

(1) 元运算是指算法中的基本操作，包括赋值、比较、算术运算、逻辑运算等。符合以下条件的元运算被称为基本运算：

- 具有明确的语义和数学定义；
- 可以在有限的时间内完成；
- 可以用有限的存储空间实现。

例如，在排序算法中，比较两个元素的大小和交换两个元素的位置是基本运算。在图像处理算法中，像素点的读取和修改是基本运算。

(2) 算法的空间复杂性指算法在运行过程中所需要的存储空间大小。可以用算法中使用的数据结构和变量所占用的空间来衡量。算法的空间复杂性和时间复杂性之间通常存在着一定的权衡关系，有些算法在空间上的需求较小，但时间复杂性较高，有些算法则相反。

(3) 确定性算法是指在相同的输入和条件下，总是能得到相同的输出结果的算法。不确定性算法则是指在相同的输入和条件下，可能得到不同的输出结果的算法。不确定多项式类型的算法是指使用不确定性算法求解问题的一类算法，可以在多项式时间内完成。

二、一种简单的算法是遍历整个数组，将所有的负元素依次移动到数组的前面，正元素依次移动到数组的后面。这个算法的时间复杂性为 O(n)，空间复杂性为 O(1)，因为只需要用到常数级别的额外存储空间。具体实现如下：

void rearrange(int arr[], int n) {
    int i = 0, j = n - 1;
    while (i <= j) {
        if (arr[i] < 0) {
            i++;
        } else if (arr[j] >= 0) {
            j--;
        } else {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
}

三、使用蒙特卡罗方法可以求解 sin(x)/x 在区间[1,2]上的定积分值。具体做法是随机生成一组点(x, y)，其中x在[1,2]之间均匀分布，y在[0,1]之间均匀分布，然后统计落在函数下方的点的个数n，用n除以总点数m，并乘以区间长度2，得到近似的积分值。代码如下：

double integrate(double (*f)(double), double a, double b, int n) {
    double sum = 0.0;
    for (int i = 0; i < n; i++) {
        double x = a + (b - a) * random();
        double y = f(x) * random();
        if (y <= f(x)) {
            sum += 1.0;
        }
    }
    return sum / n * (b - a) * 2.0;
}

double f(double x) {
    return sin(x) / x;
}

int main() {
    srand(time(NULL));
    double a = 1.0, b = 2.0;
    int n = 1000000;
    double result = integrate(f, a, b, n);
    printf("The integral of sin(x)/x from 1 to 2 is approximately %.6lf\n", result);
    return 0;
}