幂集生成函数的时间复杂性
我正在尝试找出我写的函数的时间复杂性(它会生成public static HashSet GeneratePowerSet(string input) { HashSet powerSet = new HashSet(); if (string.IsNullOrEmpty(input)) return powerSet; int powSetSize = (int)Math.Pow(2.0, (double)input.Length); // Start at 1 to skip the empty string case for (int i = 1; i
0 2024-04-16
编程技术问答社区
.NET List.sort()的时间复杂度是多少?
c#'s List.Sort() 的时间复杂性是什么 我想是o(n) 但是在我搜索很多之后,我没有得到任何准确的结果. 解决方案 /library/b0zbh7b6.aspx 此方法使用Array.Sort,它使用了QuickSort算法.此实现执行不稳定的形式;也就是说,如果两个要素相等,则可能无法保留其命令.相比之下,稳定的形式保留了相等的元素的顺序. 平均而言,此方法是O(n log n)操作,其中n为计数;在最坏的情况下,这是O(n ^ 2)操作. 其他解决方案 来自文档: 平均而言,此方法是O(n log n)操作,其中n为计数;在最坏的情况下,这是O(n ^ 2)操作. 这是因为它使用了QuickSort.虽然这通常是o(n log n),但 wikipedia上提到的,Quicksort通常更快地实际上,比其他O(n log n)算法" ) 其他解决方案 此方法使用Array.Sort方法应用 内省排序如下:
0 2024-04-14
编程技术问答社区
这些字典方法的复杂性是什么?
谁能解释以下Dictionary方法的复杂性是什么? ContainsKey(key) Add(key,value); 我试图找出我写的方法的复杂性: public void DistinctWords(String s) { Dictionary d = new Dictionary(); String[] splitted = s.split(" "); foreach ( String ss in splitted) { if (!d.containskey(ss)) d.add(ss,null); } } 我假设两种字典方法是log(n)复杂性的,其中 n 是字典中的键数.这是正确的吗? 解决方案 整体上,此例程有效地是O(M)时间复杂性,M是您搜索中的字符串数. 这是因为 dictionary.cont
2 2024-04-13
编程技术问答社区
List.Insert是否有任何性能缺陷?
给定列表: List SomeList = new List(); 做: SomeList.Insert(i, val); vs. SomeList.Add(val); 有绩效罚款吗?如果是这样,它如何取决于: - i - 插入索引 - SomeList.Count - 列表的大小 解决方案 列表类是ArrayList类的通用等效物.它使用阵列会根据需要动态增加大小的数组来实现Ilist通用界面. ( source ) 意味着内部数据被存储为数组,因此可能需要执行insert它需要移动所有元素以使空间置于空间,因此其复杂性为o(n),而add是(摊销的)恒定时间O(1)操作,因此是. 摘要 - 是的,它几乎总是会慢,并且列表获得的越大. 其他解决方案 如有疑问,请执行经验实验: List SomeList = new List(); Stopwa
0 2024-04-12
编程技术问答社区
如果字符串在.NET中是不可变的,那么为什么Substring需要O(n)时间?
鉴于字符串在.NET中是不变的,我想知道为什么它们的设计使string.Substring()花费O(substring.Length)时间,而不是O(1)? 即.折衷是什么? 解决方案 更新:我非常喜欢这个问题,我只是写了博客.请参阅 strings,不可实变和持久性 简短的答案是: o(n)是o(1),如果n不大.大多数人从微小的字符串中提取微小的子字符串,那么复杂性如何渐近地增长为 完全无关. 长答案是: 构建的不变数据结构使得对实例的操作允许重复使用原始的内存,仅少量(通常是O(1)或O(lg n))复制或新分配称为"持久"不变的数据结构. .NET中的字符串是不变的;您的问题本质上是"为什么他们不持久"? 因为当您查看通常在.NET程序中的字符串上完成的操作时,以每种相关的方式 都简单地制作一个全新细绳. 建立复杂的持久数据结构的费用和困难并不成本. 人们通常会使用"子字符串"来提取一个短字符串(例如,十或二十个字符)中的字符串中,也
0 2024-04-11
编程技术问答社区
T(n)=nT(n-1)+n关系的时间复杂度将是多少?
关系的时间复杂性t(n)= nt(n-1)+n 在我的前进中 f(int n) { c++; if(n>0) for(i=1;i = 2时).因此,我们知道下限是n!. 现在,我们需要上限.我们可以注意到一件事:t(n)= nt(n-1) + n = 2).但是我们可以轻松地证明t(n)= nt(n-1)是n!的复发关系,因此我们知道t(n)
2 2024-04-10
编程技术问答社区
在使用DP算法的同时降低Knapsack 0~1的时间复杂性
我正在使用DP算法,即将子问题值存储在2D数组中,其中一个轴 含义n项目和其他 - w值从0到W其中W是最大值 背包的容量.因此,T[n-1][W]值是我需要的最佳 计算.我已经在其他来源读到,该算法的时间复杂性是 O(nW).我的问题是:是否有可能降低这段时间的复杂性? 我找到了其他关于几乎相同事情的答案-Time-Complexity-On-01-Knapsack">如何了解降低0〜1 Knapsack的时间复杂性 我告诉我们,我们不需要用小的w值计算T[i][w],因为它们没有在最佳中使用,但是我无法正确地获得它,任何人都可以给出详细的示例吗?这会使我受益很多. 解决方案 您要填充的2D数组是W的大小W(实际上,W+1,因为值来自0..W这里的渐近复杂性).因此,要填充该数组,您至少需要进行n*W工作(即使您只是将数组初始化为所有零!). 因此,θ(nw)(紧密结合,既是o(nw)和ω(nw))是您可以在渐近算法的时间复杂性方面做的
0 2024-04-09
编程技术问答社区
分析用C语言编写的函数的时间复杂性
我在C中实现了最长的常见子序列问题.我希望比较执行解决方案和动态编程版本所花费的时间.如何找到在两个版本中运行LCS功能所花费的时间?我还可以使用Scipy在图上绘制这些值并推断时间复杂性吗? 预先感谢 剃须刀 解决方案 对于问题的第二部分:简短的答案是肯定的,您可以.您需要以方便从Python解析的格式获得两个数据集(每个解决方案).类似: x y z 在每条线上,其中x是序列长度,y是动态解的时间,z是递归解的时间 然后,在python中: # Load these from your data sets. sequence_lengths = ... recursive_times = ... dynamic_times = ... import matplotlib.pyplot as plt fig = plt.figure() ax = fig.add_subplot(111) p1 = ax.plot(sequence_
0 2024-04-08
编程技术问答社区
python的len()内置的o(1)的秘密是什么
由于Python是在C中实现的,我感到困惑的是,开发人员如何设法使Python内置len函数在恒定时间内以任何顺序运行O(1),而C的字符串函数strlen在线性时间内运行, 在). Python的内置len函数的时间复杂性是什么?如果我们要在C中编写程序,如果我们想使用快速C程序涉及序列长度,将Python的代码复制为len是最好的做法吗? 解决方案 我想您缺少一个概念,这是数据结构可以在恒定时间返回其大小的方式,即O(1). 大致想到这样的程序: void init(){ // code to initialize (or allocate memory) the container size = 0; } void add(Something something){ container.add(something); size++; } void remove(Something something){ //
2 2024-04-08
编程技术问答社区
计算位图中的连续区域是否可以改进为O(r * c)?
您将获得由卫星拍摄的表面的图像.图像是一个位图,其中水标记为'.土地以" *"为标志. '*的相邻群体形成一个岛屿. (如果水平,垂直或对角线邻居是两个'*').您的任务是打印位图中的岛屿数量. 示例输入: - .........** **......*** ........... ...*....... *........*. *.........* 输出:-5 这是我的实现,它占用O(r * c)空间,O(r * c) r是总数.排和c的总数是col. #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]
0 2024-04-08
编程技术问答社区
lseek()的复杂度是O(1)吗?
我知道我的问题在这里有一个答案: qfile seek seek seek seek performance .但是我对答案并不完全满意.即使查看了Ext4的以下实现generic_file_llseek(),我似乎也无法理解如何测量复杂性. /** * generic_file_llseek - generic llseek implementation for regular files * @file: file structure to seek on * @offset: file offset to seek to * @origin: type of seek * * This is a generic implemenation of ->llseek useable for all normal local * filesystems. It just updates the file offset to the val
0 2024-04-08
编程技术问答社区
C,西格玛的时间复杂性?
我如何找到以下代码的时间复杂性: (对不起,添加图像,一旦访问笔记本电脑,我将重新编辑我的问题) 我到目前为止所做的事情: 第一个循环迭代n次,第二次i次和第三log(i*j)次,所以简化后,我得到了: sigma从i = 0到n的i * log i + n *(j = 0到i的sigma for log I) 但是为什么这等于o(n^2 log(n))? 解决方案 近> : 在最坏的情况下: 第一个循环执行n时间. 第一个循环的时间复杂性= O(n) 第一和第二循环的时间复杂性 = 1 + 2 + 3 + 4 + ... + n = O(n*(n+1)/2) = O(n^2) 我们可以计算第三循环的复杂性,并将其乘以先前计算的复杂性,因为第三个循环不会影响前一个循环的变量(更改第一或第二个循环的任何变量). . 第三回路的时间复杂性= log(i*j) = log(i*j) = log(n*2 ) = 2log
0 2024-04-07
编程技术问答社区