Tag: 复杂性理论

为什么此代码中的时间复杂度为O（n ^ 2）？

我只是没有得到它，为什么时间复杂度是O（n ^ 2）而不是O（n * logn）？ 第二个循环每次递增2，所以不是O（logn）？ void f3(int n){ int i,j,s=100; int* ar = (int*)malloc(s*sizeof(int)); for(i=0; i<n; i++){ s=0; for(j=0; j<n; j+=2){ s+=j; printf("%d\n", s); } free(ar); }

寻找function复杂性指数

我必须根据行数找到C文件的复杂性。 我找到了行数。 但是如何判断它是否是一个复杂的文件呢？ 基于一定的价值，我必须给它一个索引。 例如，复杂性指数 – 高复杂度的5。 我可以在哪个基础上编制索引？ 例如，超过1000条高复杂的生产线将不适用于所有生产线。 是否有任何标准的方式给出条件（’超过1000行’）？ 除了任何预定义的工具，欢迎任何类型的建议。 我需要用C编程。提前谢谢。

C定向图实现选择

欢迎mon amie ， 在我的一些作业中，我觉得需要使用Graph ADT。 但是，我想拥有它，怎么说， generics 。 也就是说，无论我喜欢什么，我都希望存储在其中。 我面临的问题与复杂性有关。 我应该使用什么数据结构来表示节点集？ 我忘了说我已经决定使用Adjacency list技术 。 一般来说，教科书提到了一个链表，但据我所知，只要链表很有用并且我们需要进行搜索， 树就更好了 。 但话说回来，我们需要的是将一个节点与其相邻节点列表相关联， 那么哈希表怎么样呢？ 你能帮我决定在哪些数据结构（链表，树，哈希表）中存储节点？

我应该考虑memmove（）O（n）还是O（1）？

这可能是一个愚蠢的问题，但我想计算一个算法的复杂性，我不确定memmove（）函数要考虑的复杂性。 你能帮忙/解释一下吗？ void * memmove ( void * destination, const void * source, size_t num ); 复杂度O（num）或O（1）也是如此。 我想这是O（num），但我不确定我现在缺乏对引擎盖下发生的事情的理解。

当所有元素相同时，Quicksort的复杂性？

我有一个N个数字的数组是相同的。我正在应用快速排序。 在这种情况下，排序的时间复杂度应该是多少。 我盯着这个问题，但没有得到确切的解释。 任何帮助，将不胜感激。

查找数组中的前n个最大元素

我有一个包含唯一元素的数组。 我需要以尽可能最小的复杂性找出数组中的前n个最大元素。 到目前为止，我能想到的解决方案具有O（n ^ 2）的复杂性。 int A[]={1,2,3,8,7,5,3,4,6}; int max=0; int i,j; int B[4]={0,0,0,0,};//where n=4; for(i=0;imax) max=A[i]; } B[0]=max; for(i=1;i<n;i++){ max=0; for(j=0;jmax&&A[j]<B[i-1]) max=A[j]; } B[i]=max; } 如果有人能想出一个更复杂的更好的解决方案，我将非常感激。 而且我不打算改变原来的arrays！

n个数字中可能的三角形总数

如果给出n数字，我如何找到可能的三角形总数？ 是否有任何方法在不到O(n^3)时间内完成此操作？ 我正在考虑a+b>c ， b+c>a和a+c>b作为三角形的条件。