使用分而治之方法的最大函数比线性方法慢？

Question

我使用两个函数实现了 max 函数（给定一个数组，找到最大值）：max，它是 O(n) 和 mergeMax，我希望它是 O(lg n) 通过使用分而治之方法。我原以为 mergeMax 会随着 n 的增加而胜出，但令我惊讶的是它每次都被 max 函数打败。我说 mergeMax 是 O(lg N) 是不是错了？这是 C:

中的代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int maxValue = 0;

void mergeMax(int items[], int low, int high)
{
    if (high == low)
    {
        if (items[low] > maxValue) maxValue = items[low];
        return;
    }
    if (high - low == 1)
    {
        if (items[low] > items[high])
        {
            if (items[low] > maxValue) maxValue = items[low];
        }
        else
        {
            if (items[high] > maxValue) maxValue = items[high];
        }
        return;
    }
    int middleValue = (low + high) / 2;
    mergeMax(items, low, middleValue);
    mergeMax(items, middleValue + 1, high);
}

int max(const int items[], int itemCount)
{
    int max = 0;
    for (int i = 0; i < itemCount; i++)
    {
        if (items[i] > max) max = items[i];
    }
    return max;
}
int main(void)
{
    int itemCount = 2000000;
    printf("Generating...\n");
    int items[itemCount];
    srand(time(0));
    for (int i = 0; i < itemCount; i++)
    {
        items[i] = rand() % ((4294967295/2) + 1);
    }
    struct timespec start, end;

    clock_gettime(CLOCK_MONOTONIC_RAW, &start);
    mergeMax(items, 0, itemCount - 1);
    clock_gettime(CLOCK_MONOTONIC_RAW, &end);
    uint64_t delta_us = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_nsec - start.tv_nsec) / 1000;
    printf("O(lg n) time in microseconds: %lu. Result: %d\n", delta_us, maxValue);

    clock_gettime(CLOCK_MONOTONIC_RAW, &start);
    int maximum = max(items, itemCount);
    clock_gettime(CLOCK_MONOTONIC_RAW, &end);
    delta_us = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_nsec - start.tv_nsec) / 1000;
    printf("O(n) time in microseconds: %lu. Result: %d\n", delta_us, maximum);
}

Answer 1

您正在寻找一个具有 O(log n) 性能的函数。我可以告诉你，由于以下两个原因，找到最大值并不是一个很好的例子：

您的列表未排序，因此您需要调查列表中的所有项目 => 性能至少为 O(n)。
要么你的列表是排序的，那么你只取最后一个值=>性能是O(1)。

你能用性能 O(log n) 做些什么吗？是的，有，让我给你下面的例子：你有一个排序列表，你想插入一个新项目，确保列表保持排序。然后，您可以使用二进制搜索算法来查找需要插入该新项目的位置。

Answer 2

考虑有 1024 个项目的情况。当 mergeMax 调用 1024 项时，它会将它们分成两段并调用 mergeMax 两次，每次调用 512 项。

这两个 mergeMax 调用将调用 mergeMax 两次，因此总共调用四次，每次调用 256 个项目。这四个调用将调用 mergeMax 两次，因此总共调用八次，每次调用 128 个项目。这八个调用将生成 16 个调用，每个调用包含 64 个项目。这 16 个调用将生成 32 个调用，每个调用包含 32 个项目。这 32 个调用将生成 64 个调用，每个调用包含 16 个项目。这 64 个调用将生成 128 个调用，每个调用包含 8 个项目。这 128 个调用将生成 256 个调用，每个调用包含 4 个项目。这 256 个调用将生成 512 个调用，每个调用有 2 个项目。

在 2 个项目中，mergeMax 直接处理这两个项目，不再生成任何调用。

在这 512 次调用中的每一次调用中，最多考虑 2 个项目。因此，为找到最大值所做的工作量仍然是 1024 次测试。什么都没有保存。

此外，还有 512 次最终调用，之前有 256 次，之前有 128 次，然后是 64、32、16、8、4、2 和 1。总共有 1023 次调用 mergeMax , 1022 比简单调用 max 还多。因此，除了 1024 次测试之外，您还增加了 1022 次函数调用的开销。

所以当然 mergeMax 更慢。

除了调用深度，mergeMax 没有任何对数，调用深度是一次有多少嵌套调用。

使用分而治之方法的最大函数比线性方法慢？

Max function using divide and conquer approach is slower than linear?

c

complexity-theory

divide-and-conquer