我需要在k的模型上从最小到最大排序一个列表，我只能用一种纯粹的迭代方式来完成这个任务，而不是递归的。基本上我唯一能得到的是：
public static void sortMod(int [] a, int k)
如果只使用n个log运行时和O(1)空间，并且不创建任何新的数组，我如何做到这一点？
浏览 6提问于2022-07-11得票数 -1
我遇到了用于子字符串搜索的KMP算法，并在python中实现了它。后来，我发现in运算符也可以用来解决这个问题，我决定比较它们的性能。令我惊讶的是，in比KMP算法快得多，我决定仔细看看in。 我发现in在一个字符串中实现了__contains__方法，该字符串用于Datamodel doc中建议的包含检查。但不能进一步解释为什么它更快。 下面是我的KMP算法的实现： def lps(pattern):
start_ind = 0
lps_list = [0]
for j in pattern[1:]:
if(j == pattern[start_in
浏览 18提问于2019-04-06得票数 7
回答已采纳
2回答
假设我正在分析一个算法，我想计算比较数。
假设结构是这样的：
if (a == b){
...
}
else if (a == c) {
...
}
else if (a == d) {
...
}
else {
...
}
计算比较的最好方法是什么？
我想这就是解决之道：
int compare = 0
compares++; //will always do the first compare
if (a == b){
...
}
else if (a == c) {
compares++; //add another because we got here
浏览 1提问于2014-11-14得票数 0
2回答
查找LCM的代码复杂度是多少？这种复杂性永远不会是O(n)。此外，根据输入的不同，步骤也会有所不同。谢谢。
public static int findGCD (int a, int b) {
int c;
do {
c = a % b;
if (c > 0) {
a = b;
b = c;
}
} while (c != 0);
return b;
}
浏览 0提问于2013-06-09得票数 0
回答已采纳
1回答
求配对法的时间复杂度
、、、、
我必须编写代码来获取一个具有奇数个元素的已排序双精度数组，找到它们之间距离最短的值对，然后返回剩余值，它被认为是“奇数”。下面是我写的代码，它可以工作并返回正确的值。
有人能帮我找出我使用的算法的时间复杂度吗？我试过了，但这真的很让人困惑。
public static Double findPairs(Double[] data, int i, int j, int k, int count) {
Double oddNumber = -1.;
if ((k < data.length) && (diff(data[i], data[j]) <=
浏览 1提问于2015-02-18得票数 1
我是这么认为的，因为上限是2^n，并且假设这两个机器都是有限的机器，那么n状态NFA和具有2^n或更少状态的DFA的交集将是有效的。
我说错了吗？
浏览 3提问于2010-10-15得票数 3
5回答
有没有人对常见搜索和排序算法的Java代码实现有很好的参考。
给猫剥皮的方法有很多种(在网上很容易找到各种算法的Java代码)，但是Java中有没有实现这些算法的最有效方法的列表呢？
例如，有，但大多数实现都是用C/C++实现的。
干杯!
浏览 0提问于2012-04-15得票数 3
回答已采纳
2回答
我想问这个问题：
下面哪个时间复杂性代表了更好的最差运行时间？
(a) O(lg(n!))
(b) O(n)
(c) O(n平方公里)
(d) O(lg(lg(N)
(e)上述任何一项
答案： (d)
根据选项，选项d应该是最好的情况，因为它花费最少的时间。
根据备选方案，备选方案c应该是最坏的情况。
如果问题是关于最坏的情况，为什么答案是(d)？
浏览 6提问于2022-05-30得票数 -3
3回答
我目前正在钻研学习C语言，虽然我还没有深入到这个过程中，但我想要一些功能齐全的windows应用程序的例子，这些应用程序的源代码并不太复杂--比如计算器/记事本？
有谁有任何链接，我可以找到一些好的例子，除了‘转换kgs到石头’或计算速度从时间和距离？
肯定会对我的灵感有所帮助。:D
谢谢。
浏览 1提问于2011-06-08得票数 0
回答已采纳
考虑一下an^2 + bn + c。我理解对于大型n来说，bn和c变得微不足道。
我还了解到，对于大型n，2n^2和n^2之间的差异与n^2和n*log(n)之间的差异相比是微不足道的。
然而，2n^2和n^2之间仍存在2阶的差异。这在实践中重要吗？还是人们只考虑没有系数的算法？为什么？
浏览 4提问于2014-12-01得票数 0
public static int partitionsimple_hoare(int[] arr,int l , int h){
int pivot = arr[l];
int i = l-1;
int j = h+1;
while(true){
do{
i++;
}while(arr[i]<pivot);
do{
j--;
}while(arr[j]>pivot);
if(i<j){
s
浏览 0提问于2017-09-21得票数 1
5回答
我正在学习算法分析。我很难理解O、Ω和Θ之间的区别。
定义它们的方式如下：
f(n) = O(g(n))意味着c · g(n)是f(n)的上界。因此，存在一些常量c，使得f(n)总是≤c · g(n)，对于足够大的n (即，对于某些常数n0来说，n ≥ n0 )。
f(n) = Ω(g(n))意味着c · g(n)是f(n)的下界。因此，存在一些常量c，因此对于所有n ≥ n0，f(n)总是≥c · g(n)。
f(n) = Θ(g(n))意味着c1 · g(n)是f(n)的上界，而c2 · g(n)是f(n)上的下界，对于所有n ≥ n0都是这样。因此，存在常数c1和c2
浏览 8提问于2009-12-25得票数 34
回答已采纳
3回答
我知道最坏的/avg/最好的情况是用来确定算法的复杂度时间成一个函数，但是它是如何用于渐近分析的呢？我理解上/紧/下界(大O，大欧米茄，大θ)是用来比较两个函数，并看到它的极限(增长)是从另一个角度看的，随着n的增加，但我很难看出最坏/avg/最佳情况大O和渐近分析之间的区别。把我们的最坏/avg/最佳情况大O计算到渐近分析和测量界，我们到底能得到什么呢？我们会用渐近分析来具体比较最坏/avg/最佳情况下的两种算法吗？如果是这样的话，我们是否对算法1和算法2使用函数f(n)，或者对算法1为f(n)的每一种算法进行单独的渐近分析，并试图找到一些c*g(n)，使得=> f(n)和c*g(n)
浏览 5提问于2013-08-11得票数 0
回答已采纳
2回答
您将得到一个字符串，例如"acdfdcqqc"，需要创建一个算法来查找最大的回文子字符串，在我们的例子中是"cdfdc"。设计O(n^2)算法很容易，方法是创建一个大小为2n的数组，每次计算具有中心点的最大回文的长度，即：
a - c - d - f - d - c - q - q - c
1 0 1 0 1 0 5 0 1 0 1 0 1 4 1 0 1
对于每个2n个可能的起点，我向两个方向移动，找出从那个位置开始的最大回文的长度。因此，对于每个2n运算，我最多做O(n)运算，因此O(n^2)时
浏览 5提问于2016-07-30得票数 2
回答已采纳
1回答
在数据子集之间进行选择
、、、、
假设我在它们的子集之间有{a,b,c}：
SUB={{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
我希望在数组中包含完整的成员，例如：
array[0]={{a,b,c}}
array[1]={{a,b},{c}}
array[2]={{a},{b,c}}
我的意思是，我想提取没有任何公共成员的集合，而一个数组包含所有成员
我想减少复杂度时间，如果我搜索整个，它将是n*n，但我认为递归编写将降低时间复杂度，但我不能解决如何编写递归的时间复杂度。这个例子有3个成员，我想n个成员。
我知道如何提取子集，但我不知道如何用这个条件填充我的数组。
浏览 1提问于2011-11-30得票数 0
1回答
查找索引位置函数
、、
以下功能的复杂性是什么？
def find_set(string, chars):
schars = set(chars)
for i, c in enumerate(string):
if c in schars:
return i
return -1
print(find_set("Happy birthday", "py"))
在这种情况下，返回一个1，因为H位于CHEERIO的索引1。
是否有可能进一步优化此功能？
浏览 3提问于2015-02-03得票数 1
回答已采纳
如果我们有一个线性算法(例如，查找一个数字是否存在于给定的数字数组中)，这是否意味着Omega(n) = n？步骤数为n。我能做的最紧的界限是c*n，c = 1。
但据我所知，Omega还描述了最好的情况场景，在本例中是1，因为搜索的元素可以位于数组的第一个位置，并且只占一个步骤。所以，根据这个逻辑，Omega(n) = 1。
哪个变体是正确的，为什么？谢谢。
浏览 0提问于2018-07-06得票数 2
回答已采纳
2回答
我试图解决一个编程问题，在这个问题中，我需要实现以下算法(粗略地)：
有两个节点，即A、B、C等。
每个节点都可以在其中包含多个项，例如a、b、c、x、y、z等。
A [a, b, c, x, y, z]
B [a, b, c]
C [x, y, z]
节点可以有无限多的节点和项，节点可以在其中包含任意数量的项(但同一项不会再次重复)。
我要做的是，根据节点中的公共项，在节点之间创建继承关系。所以，在上面的例子中，A应该比B和C有更高的继承性，换句话说，A是主人，B和C是奴隶。
因此，我在想，如果我可以根据公共项目从节点上构建一棵树，那么对我来说就更容易了。但我不知道该用哪种算法。有人知道
浏览 8提问于2013-09-09得票数 3
回答已采纳
1回答
我有一个关于渐近复杂性的问题，特别是大O符号。 从数学上讲:我们有一个函数T(n)它的输出:我们的算法所花费的时间。 例如T(n) = 1000 + 10n。我们选择一个简单函数F(n) =n，并且对于一些大的自然数N和常数C，T(n) <= C.F(n)，它等价于T(n)属于O(f(n ) ) (其中T其中一个由C.F(n)控制的函数集)。 我的具体问题:我没有得到上界的点，从一个特定的输入N，所有的T(n)点都是F(n)点的上界。 在计算机科学和大O表示法中，这种数学近似和最坏-最好情况的复杂性之间有什么关系 ?
浏览 37提问于2021-07-15得票数 1
1回答
平滑排序算法用在哪里？
、、、、
在我的大学学习算法的时候，我遇到了一个叫做Smoothsort的算法。这是一个很好的算法，因为它是一个自适应算法，时间复杂度可以从线性复杂度到线性复杂度变化，它也是一种就地算法。然而，关于该算法的资源非常稀缺，并且这些可用的资源非常难以理解。然而，我张贴这个问题的原因是为了了解用例，以及何时应该使用它，什么时候不应该使用它？
这就是我想知道的一切，非常感谢你回答或评论这个问题。
浏览 10提问于2020-09-13得票数 2
我在大学里有一个项目，用Linux或Ubuntu算法搜索文件或文件夹。我得把它适应于mac和windows。
algorithm使用哪种算法？或者这些操作系统用来搜索目录中的任何文件文件夹.
浏览 0提问于2014-08-23得票数 5
我很困惑，我以为在最坏的情况下运行时间使用Big，而最好的是使用Ω？谁能解释一下吗？
(lg n)不是最好的情况吗？(nlg n)是最坏的情况吗？还是我误会了什么？
在大小为n的堆上，最大Heapify最坏的运行时间是Ω(lg n)。(提示:对于有n个节点的堆，给出节点值，使Max-Heapify在从根到叶的路径上的每个节点上被递归调用。)
编辑:不，这不是作业。我正在练习，这有一个答案，键买我迷茫。问题4(6.2-6)
编辑2:所以我误解了这个问题，而不是关于大O和Ω？
浏览 4提问于2013-03-14得票数 10
回答已采纳
1回答
我是在扩展我之前的问题，
我对提高子字符串搜索实现的性能感兴趣，
我上一个问题中的一些答案指出，子字符串搜索是通过使用基于by算法的快速搜索来实现的，下面是
更多的答案向我指出了一个蟒蛇实现的Boyer算法，Rabin算法.
使用这些算法( be，Rabin-Karp)嵌入c代码作为子字符串搜索的良好实现是否有效？
浏览 1提问于2012-09-04得票数 1
回答已采纳
2回答
对于算法，最好/最坏情况的界限是如何联系的？最坏情况是否与上界同义，而最佳情况是否与下限同义？或者你至少可以从另一个中派生出一个？或者它们是完全没有关系的？
浏览 6提问于2015-06-22得票数 2
/*
Returns true is the two strings are permutations of each other.
Time Complexity; O(nlog n) -> because of the java utils array sort
Space Complexity; O(1)
*/
public boolean isPermutationOptimized(String one, String two) {
if (one.length() != two.length()) {
return
浏览 17提问于2021-10-05得票数 0
回答已采纳
2回答
假设我们有一个包含N个元素的排序列表。我在一本教科书中读到，确定这个列表是否有重复项的算法必须至少执行n-1比较(这意味着n-1是比较次数的下限)。我不明白这一点，因为假设第1和第2元素是重复的，那么算法只需在执行一个比较之后返回'yes‘。我做错什么了？有没有关于n-1下界的简单证明？
浏览 8提问于2019-11-12得票数 0
回答已采纳
8回答
我有9个矩阵形式的值，需要在模拟过程中计算这些值的中位数。
我在C++中使用快速排序(即qsort())，这会导致进程运行缓慢(因为这个进程会迭代几次)。
有没有我可以使用的更好的排序算法？
浏览 4提问于2009-07-30得票数 1
回答已采纳
1回答
我开始学习函数式编程，我试着比较用命令、函数式、并行编程和使用Collection和Lambda表达式编写的不同算法。为了明确我的问题，避免分享我正在研究的长算法。我将以著名的修正Fibonacci算法(Euler问题2)为例：
问题是：http://projecteuler.net/problem=2
//Iterative way:
int result=2;
int first=1;
int second=2;
int i=2;
while (i < 4000000)
{
i = first + second;
if (i % 2 == 0)
{
浏览 0提问于2013-12-08得票数 7
1回答
我最近遇到了排序技术，特别是“插入排序”。
虽然逻辑和方法是相当容易理解的，但实际的功能似乎有点复杂(如下所示)。
void InSort(int AR[], int size)
{
int tmp,j;
AR[0]=INT_MIN; //defined in limits.h , basically the smallest possible value
for(int i=1;i<size;i++)
{
tmp=AR[i];
j=i-1;
while(tmp<AR[j])
浏览 0提问于2015-01-19得票数 2
我有两种矩阵乘法算法-一种比另一种更有效-并在计算N = [500, 1000, 1500, 2000, 2500]的两个NxN矩阵的乘积时测量了这两种算法的速度。
现在，我想展示一下N在速度方面的一般改进。我该怎么做呢？
浏览 0提问于2017-10-27得票数 0
我刚刚注意到，每次启动#hash时，的返回值都会发生变化：
$ irb
2.0.0-p353 :001 > "".hash
2313425349783613115
2.0.0-p353 :002 > exit
$ irb
2.0.0-p353 :001 > "".hash
4543564897974813688
2.0.0-p353 :002 > exit
我查看了MRI的来源，想知道为什么会发生这种情况：
st_index_t
rb_str_hash(VALUE str)
{
int e = ENCODING_GET(str)
浏览 4提问于2014-04-28得票数 4
回答已采纳
我试图简化和比较非常大的布尔表达式的等价性。我传统上使用来自sympy的sympy来简化表达式，然后比较这两个字符串的等价性。只有当表达式包含8个或更少的元素时，这才能正常工作。如果我试图比较两个有15+元素的表达式，每个表达式只挂起(因为所需时间呈指数增长)。是否有任何Python包或其他迂回方式来尝试完成这一任务？
用随机示例更新
Exp1 =‘A区-B&(C-D-D-E-)&F
Exp2 =‘A&B&C&(D&B&B&C&(D&B&C&(D&B&C&(D、E、E、O&a
浏览 6提问于2019-12-05得票数 1
4回答
我正在研究随机快速排序算法。我意识到这个算法的运行时间总是被表示为“预期运行时间”。
指定或使用“预期运行时间”的原因是什么？为什么我们不计算最坏的或者平均的情况呢？
浏览 1提问于2011-10-26得票数 8
回答已采纳
1回答
我正在做一个项目，让一个模拟的机器人通过移动到预先定义的“传感位置”来探索未知的、但有模式的环境(如办公楼)。换句话说，在每个点上，机器人必须从可用的可见位置选择要移动到的新位置。我们的最终目标是让机器人学习如何利用环境中的模式来优化全局探索时间。
机器人通过基于关于该位置的许多已知特征(例如到该点的距离、从该点到所有其他点的平均距离、已经探索的点周围的区域等)的线性组合来为其提供效用分数，从而选择下一个移动到哪个位置。我的目标是优化这个效用函数的权重，以提供最快的时间来探索整个环境。
因为分数取决于整个探索路径，所以我不想在探索过程中改变权重。为了测试权重组合，我希望模拟的机器人使用这些权重
浏览 3提问于2011-03-25得票数 1
回答已采纳
2回答
预测自动补全背后的算法/理论？
、、、、
简单单词自动完成功能仅显示与已经键入的字符匹配的单词列表。但我想根据单词出现的概率对自动完成列表中的单词进行排序，这取决于之前键入的单词，依赖于文本语料库的统计模型。为此，我需要哪些算法和数据结构？你能给我一些好的教程的链接吗？
浏览 0提问于2012-07-12得票数 13
回答已采纳
1回答
我创建了一个C++程序，该程序输出算法的输入大小与执行时间(微秒)，并将结果写入.csv文件。在LibreOffice Calc中导入.csv并绘制图形时，
我注意到，即使我搜索的元素不在数组中，对输入大小最大为10000的二进制搜索的运行时间也是恒定的。类似地，对于相同的输入大小，合并排序似乎在线性时间内运行，而不是在所有情况下运行的线性对数时间。
插入排序和冒泡排序运行得很好，输出图非常接近它们最坏的情况下的二次复杂性。
我从一个文件中提供了输入数组。对于n= 5，文件的内容如下所示。每行代表一个输入数组：
5 4 3 2 1
4 3 2 1
3 2 1
2 1
1
运行插入排序的
浏览 1提问于2018-10-08得票数 0
1回答
寻找复杂度的上下限
、、、、
我想找到这个算法复杂度的下界和上界。
1: for all i=1 to n*n do
2: for all j=i to 2*i do
3: output “hello world”
4: end for
5: end for
将其写成求和并简化为
f(n) = 0.5*n^4 + 1.5*n^2
复杂度的上限似乎是O(n^4)，因为0.5*n^4是最重要的元素。
对于复杂性的下限，我使用了以下公式
f(n) = Ω(g(n)) if f(n) >= c * g(n), where c > 0
对于0<c<1，它的下界似乎是Ω(n^3)
我的推理对这两
浏览 3提问于2018-05-02得票数 0
3回答
根据我(简要地)读到的，Java和Python看起来都在他们的标准库中使用timsort，而C的stdlib中的排序方法被称为qsort，因为它曾经是快速排序。
今天，典型的语言在他们的标准库中实现了什么算法，为什么他们选择这种算法？另外，C语言是否偏离了快速排序？
我知道这个问题缺乏“我面临的实际问题”，对一些人来说似乎是开放的，但知道如何/为什么选择某些算法作为标准似乎非常有用，但相对没有教过。我也觉得似乎是一个深入的答案，解决了特定于语言的问题(数据类型？)和特定于机器的(缓存命中？)将提供更多关于不同语言和算法如何工作的洞察力，而不是uni所关心的解释。
浏览 0提问于2013-05-01得票数 7
3回答
我想知道在Python中确定内置方法背后的大O值的理由。考虑到以下操作：
i_arr = ['1','2','5','3','4','5','5']
s_arr = sorted(set(i_arr))
我的基本原理是，这是sorted(set) = n^2，意思是两个嵌套循环。
根据建议，我在Python源代码中挖掘了更高级别的模块，这是我最初函数的一部分：
def sorted(lst):
l = list(lst)
l.sort()
浏览 7提问于2017-05-03得票数 2
回答已采纳
2回答
我试图回答这个关于算法的问题，但我不明白这可能是什么。我没有任何例子可以提供给你们，我和你们分享的和我分享的一样：
“如果最坏情况下的X算法的复杂度等于最佳情况下的Y算法的复杂度，那么这两种算法中哪一种更快?请解释为什么！”
浏览 2提问于2021-07-01得票数 0
回答已采纳
1回答
我开始学习的数据结构和算法。
对于第二个问题，他们要求我们实现一个算法来找到数组中的两个最高值。作为另一个问题，他们增加了以下练习：
运动休息。在1.5n比较中，在数组中找到两个最大的元素。
我不知道1.5比较到底是什么意思。我在谷歌上搜索过，但没有找到算法比较的解释。
有没有一个网站有一些比较的例子？
浏览 0提问于2021-02-15得票数 0
9回答
我想知道冒泡排序最好的情况是什么？例如，可能存在这样一种情况，其中可能没有对所说的最后2次传递的交换。我正在用C语言编写我的程序。假设我有一个由5个元素组成的数组，我给出的元素是1，2，5，4，3，那么在最后的2次传递中不会有任何变化？
浏览 2提问于2009-08-31得票数 10
我有一个无序的n项目列表，我正在试图找到该列表中最常见的项目。我编写了以下代码：
def findFrequant(L):
count = int()
half = len(L)//2
for i in L:
for j in L:
if i == j:
count += 1
if count > half:
msg = "The majority vote is {0}&
浏览 2提问于2015-09-26得票数 0
回答已采纳
1回答
我想看看数组中每一个相邻数之间的差异是否与另一个数组相同，或者它的旋转，例如
A = {1,2,4}, so the differences are {1,1,2}
B = {4,6,7}, the differences are {1,2,1}
如果{1,2,1}中的所有元素都顺时针方向移动，则结果是{1,1,2}，这是正确的.
到目前为止，我将差异转换为字符串，然后查看第二个数组的差异是否存在于与自身连接的第一个数组中。
valid if "1 2 1" is in "1 1 2 1 1 2"
到目前为止，我的代码看起来是数组的长度，两者都有相同的长度。
浏览 0提问于2014-11-12得票数 0
回答已采纳
这是从流行的书“算法简介”中摘录的。作者指出，在最坏的情况下，任何比较排序算法都需要Ω(nlgn)比较。以气泡排序算法为例，在最坏的情况下，我们有一个上界O(n^2)。欧米茄代表下界或最小界，因此，最坏情况的下界不也是Ω(n^2)吗？在最坏的情况下，气泡排序怎么会有一个下限，比如建议的Ω(nlgn)，而不是n^2？在最坏的情况下，性能泡沫排序不能采取至少nlgn。
浏览 6提问于2014-09-17得票数 2
回答已采纳
我有一个部分约束(在参数中)最小化问题，我目前正在使用Octave的fminunc函数来解决这个问题，但是在目标函数本身中，约束是通过使用if语句来实现的，如果任何约束被违反，就会产生一个真实的最大成本。
但是，该问题也可以通过显式提供约束的参数的上、下界fmincon来解决。我可能还可以使用其他更“复杂”的函数，比如sqp来解决这个问题。
我要解决的问题是：-找到“a”到“f”这样的值
C1 - a = C2 * K
C3 + b = C4 * K
C5 - c = C6 * K
C7 - d = C8 * K
C9 + e = C10 * K
C11 - f = C12 * K
wher
浏览 1提问于2021-07-02得票数 0
例如，当我们考虑函数f(n)=O(g(n))或类似于Big Theta时，我知道Big O是一个上界，Big Theta是一个紧界。但是，我们如何知道使用Big theta表示法而不是Big O表示特定的算法会更好呢？
例如，选择排序的时间复杂度是N^2的Big Theta而不是N^2的Big O，为什么？
浏览 0提问于2017-02-02得票数 0
使用randomize_quicksort()，我们知道平均情况复杂度是O(nlgn)，因为我们选择了随机过程的支点。然而，当我研究随机化选择算法时，我们也随机选择了类似于randomize_quicksort()的支点，在最坏的情况下，我们得到了O(n^2)的复杂性。我不明白是什么使它在二次时间内运行，尽管我们使用相同的策略来选择支点元素。
谢谢
浏览 3提问于2016-11-28得票数 1
3回答
壳体分类分析
、、、
我正在读一本关于算法的书，书中提到了对shell排序算法的分析，如下所示：
使用Shell的增量最坏的运行时间是Theta(n平方).
证明不仅需要显示最坏情况下运行时间的上限，而且还需要显示某些输入实际上需要作为Omeaga(n平方)时间来运行。通过构造一个坏的情形，我们首先证明了下界。
我对上述的问题是：
，为什么作者提到坏的情况来检查下界？我教过要达到下限，我们应该采取最好的情况，恳请澄清以上。
谢谢!
浏览 6提问于2011-09-09得票数 2
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
腾讯云开发者
