Tag: 时间复杂度

优化性能 – 在图形上实现自定义算法

对于我的大学任务，我需要提出一种算法，找到具有相同权重的最大边数的生成树。 可以在此处找到任务的描述： 查找具有相同权重的最大边数的生成树 。 在那里你还可以看到我用C语言实现的upvoted解决方案（由@mrip建议）。 我已在本地计算机上测试了代码，并在不同的数据集上提供了正确的输出。 但是，当我将解决方案上传到高程系统时，我发现程序完成时间比参考时间长3倍。 这是项目中的两个文件。 我当然添加了详细的评论： header.h //struct for subsets used in MST Kruskal algoritm typedef struct subset { int parent; int rank; } subset_t, *subset_p; //struct for storing graph edges typedef struct edges { int src; int dest; int weight; } edges_t, *edges_p; //struct for storing weights and number of their […]

如何测量C代码的运行时间比较？

示例代码1： const int N=100000; for(int j=0;j<N;j++){ arr1[j] += a1[j]; arr2[j] += a2[j]; } 示例代码2： for(int j=0;j<N;j++){ arr1[j] += a1[j]; } for(int j=0;j<N;j++){ arr2[j] += a2[j]; } 我需要计算这些代码块的运行时间。 是否有任何工具（基准）来计算它？

分析用C编写的函数的时间复杂度

我在C中实现了最长公共子序列问题。我希望比较执行解决方案的递归版本和动态编程版本所花费的时间。 如何在各种输入的两个版本中找到运行LCSfunction所需的时间？ 我也可以使用SciPy在图表上绘制这些值并推断时间复杂度吗？ 提前致谢， 剃刀

列出所有排列的代码的时间复杂度？

例如，如果输入字符串是“ABC”，则输出应为“ABC，ACB，BAC，BCA，CAB，CBA”。 这是我的方法： #include #include #include void print(char str[],int visited[],int index,char temp[],int len) { if(index==len) { temp[index]=’\0′; printf(“\n%s”,temp); return; } for(int i=0;i<len;i++) { if(!visited[str[i]-'A']) { visited[str[i]-'A']=1; temp[index]=str[i]; print(str,visited,index+1,temp,len); visited[str[i]-'A']=0; } } } int main() { int visited[20]={0}; char temp[20]; char str[] = "ABCD"; int len=strlen(str); print(str,visited,0,temp,len); getch(); return 0; } 我已经使用了一个访问过的数组来避免重复字符。 这段代码的复杂性是什么？

C中的二元向量和矩阵操作

我试图在C中实现一个数据结构，这将允许我有效地操作**二进制**矩阵（仅包含1或0）。 我将解释我必须对此矩阵应用哪些操作，并想知道使用哪种最佳数据结构？ 操作在字段F_2中完成（这意味着1 + 1 = 0，其他操作保持不变）。 我有一个叫做H k * n矩阵（ k < n ）。 最多， k = 2325， n = 3009。 我必须对此矩阵执行的操作是： 我将仅使用行交换和行添加来部分对角化它。 一旦完成，我将不再使用行操作，并将在此矩阵上运行大量（！）列添加 （我的意思是“很多”是关于（（nk）/ 2）³列添加） 我正在考虑矩阵的数据结构： 对于矩阵系数，我考虑在一个单个unsigned int中一次存储多个位的序列。 例如，我可以将序列(11001011)存储到uint8_t 203 （从二进制转换为十进制） 这是个好主意吗 ？ 如果我这样做，我有两个选择： 我可以使用uint16_t或uint64_t系数在许多4 * 4或8 * 8子矩阵中分割我的矩阵H. 这是一个很好的选择（在时间效率方面），如果是，是否更好地使用uint16_t或uint64_t ？ 另外我在考虑将每一行存储在多个uint32_t或uint64_t ，然后操作我的部分对角化。 接下来切换到将矩阵编码为n列向量以处理剩余操作的结构。 你认为这更有效吗？ 无论我使用什么方法，我都必须有效地访问unsigned int的第n位（ uint16或64 ）。 我怎么做 ？

可以计算位图中的连续区域是否可以改善O（r * c）？

您将获得由卫星拍摄的表面图像。图像是位图，其中水由’。’标记。 和土地用’ * ‘标记。 相邻的’ * ‘组成一个岛屿。 （如果它们是水平，垂直或对角线的邻居，则两个’ * ‘相邻）。 您的任务是打印位图中的岛数。 示例输入： – ………** **……*** ……….. …*……. *……..*. *………* 输出： – 5 这是我的实现，它采用O(r * c)空间和O(r * c)空间，其中r是总数。 行和c是cols的总数。 #include #define COLS 12 void markVisted(char map[][COLS], int visited[][COLS], int row, int col, int rowCount) { if((row = rowCount) || (col = COLS) || (map[row][col] != ‘*’) […]

这个基本算法O（n）怎么样？

int G(int a[], int n) { int x=0, i, j; for(i=1; i<n; i=i*2){ for(j=0; j<i; j++) x += a[j]; } return x; } 最坏的情况如何严格限制在该算法O（n）上。 第一个循环是不执行O（log（n）次，第二个循环执行O（n）次是否给出O（n logn）？

Ruby方法的大O表示法？

我怎样才能找到Ruby方法的复杂性？ 例如长度 ？ 如果我查看源代码，我会看到： static VALUE rb_ary_length(VALUE ary) { long len = RARRAY_LEN(ary); return LONG2NUM(len); } 但我不知道如何阅读，以找到大O符号。

如何找到while循环的时间复杂度（Big O）？

代码1 int i = 0; int j = 0; while(i < n){ while(j < n){ printf("{%d,%d}",arr[i],arr[j]); j++; } i++; j = 0; printf("\n"); } 代码2 int result = 0; int i = 0; while (i = n / 2 && i < n){ result += arr[i]; i += 1; } } printf("%d\n", result); 我只知道如何用for循环找到时间复杂度，但我不确定while循环。 如果有人能帮助我找到每个代码的总运行时间，将不胜感激。

权力的时间复杂度（）

我实现了这个函数power() ，它接受两个参数a和b并计算一个b 。 typedef long long int LL; LL power(int a,int b) { int i = 1; LL pow = 1; for( ; i <= b ; ++i ) pow *= a; return pow; } 给定：a b落在long long int的范围内。 问题：如何降低算法的时间复杂度？