Tag: big o

列出所有排列的代码的时间复杂度？: 例如，如果输入字符串是“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; } 我已经使用了一个访问过的数组来避免重复字符。这段代码的复杂性是什么？

这种独特的字符串函数的执行时间是否从简单的O（n ^ 2）方法中减少了？: 推断字符串是否包含所有唯一字符（并且不使用任何其他数据结构）的通用算法表示要遍历字符串，针对搜索匹配的整个字符串迭代每个字母。这种方法是O（n ^ 2）。下面的方法（用C语言编写）使用偏移量来迭代字符串部分，因为例如在短字符串中没有理由用第一个字符作为第一个字符测试最后一个字符。我的问题是：算法的运行时间是O（n！）还是O（nlogn）？ #include int strunique(const char *str) { size_t offset = 1; char *scout = (char *)str, *start; for (; *scout != ‘\0’; ++scout, ++offset) for (start = (char *)str + offset; *start != ‘\0’; ++start) if (*start == *scout) return 0; return 1; } int main(void) { printf(“%d\n”, […]

Big O表示法运行时: 我已经获得了一些代码来解决他们的大O运行时间，有人可以告诉我，我是否在正确的轨道上？ //program1 int i, count = 0, n = 20000; for(i = 0; i < n * n; i++) { count++; } 是O（n ^ 2）？ //number2 int i, inner_count = 0, n = 2000000000; for(i = 0; i < n; i++) { inner_count++; } 这是一个O（n）？ //number3 for(i = 0; i < n; i++) { for(j […]

有没有任何方法可以将矩阵乘以O（n）复杂度？: 我想将两个矩阵相乘，但三重循环具有O（n 3 ）复杂度。动态规划中是否有任何算法将两个矩阵与O（n）复杂度相乘？好吧，我们不能得到最好的O（n 2.81 ）编辑：但有没有任何解决方案，甚至可以将结果近似到一些特定的否。列和行的矩阵我的意思是我们得到O（n 2.81 ）中最好的一个复杂的解决方案，但结果却很完美但是如果有任何解决方案甚至近似矩阵的乘法，因为我们有因子近似等公式。如果有任何你知道它会帮助我问候。