相关疑难解决方法(0)

我更喜欢尽可能少的正式定义和简单的数学.

问题

如何找到算法的时间复杂度？

在SO上发布问题之前我做了什么？

我走过了这个,这和许多其他链接

但是,我没有能够找到关于如何计算时间复杂度的明确而直接的解释.

我知道什么 ？

假设代码如下所示:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

说一个像下面这样的循环:

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');
}

int i = 0; 这只会执行一次.实际计算时间i=0而不是声明.

我<N; 这将执行N + 1次

i ++; 这将被执行N次

所以这个循环所需的操作数量是

{1+(N + 1)+ N} = 2N + 2

注意:这仍然可能是错误的,因为我对计算时间复杂度的理解没有信心

我想知道什么？ …

我有一个巨大的数据库表,有n个整数区间(例如{1-5},{4-16},{6434-114343}),需要找出哪些区间相互重叠.在SO上有很多 类似的问题,但不同之处在于我需要分别为每个区间返回一组重叠区间.

      ------------------ A -------------------
    ------ B -------               ----- D -----
          --------- C --------- 

对于这个例子,输出将是 A:{B,C,D} B:{A,C} C:{A,B} D:{A}

最坏的情况是,所有间隔可能相互重叠,产生大小为O(n ²)的输出.这并不比天真的解决方案好(比较每对间隔).然而,在实践中,我知道我的间隔很少会与其他间隔重叠,当它们发生时,最多只有5个其他间隔.

鉴于此信息,我该如何解决问题？(最好,我想要一个SQL查询解决方案,因为数据在数据库中,但我认为只有常规的算法解决方案是可能的.)

我需要设计一种算法，该算法将对仅包含数字-1,0,1的数组进行排序，而不使用任何临时变量或数组，并且仅使用交换，我想出了以下方法，我不确定是否是上）。

#include <stdio.h>
#define MAXSIZE 10

int main()
{
    int array[MAXSIZE];
    int i, j, num = 8, temp;

    int list[] = {-1,0,-1,0,1,1,0,1};

    int size = sizeof(list)/sizeof(list[0]);
    for (int i = 1; i < size; i++) {

        if (list[i] < list[i - 1]) {
            list[i] = list[i] + list[i - 1];
            list[i - 1] = list[i] - list[i - 1];
            list[i] = list[i] - list[i - 1];
            i = 0;
        }
    }

    printf("Sorted array is...\n");
    for (int i = 0; i …