在 Big-O 表示法中，O(N) 和 O(2N) 描述了相同的复杂度。也就是说，O(2N)的算法时间或空间复杂度的增长率本质上等于O(N)。尤其是与复杂度为 O(N^2) 的算法（给定极大的 N 值）相比，这一点尤其明显。O(N) 呈线性增加，而 O(N^2) 呈二次方增加。
所以我理解为什么 O(N) 和 O(2N) 被认为是相等的，但我仍然不确定是否将这两者视为完全相等。在输入数量 N 为 100 万或更多的程序中，在我看来，将时间复杂度减半实际上会节省大量时间，因为程序可能会少执行数百万个操作。
我正在考虑一个包含两个 for 循环的程序。每个 for 循环都会迭代一个非常大的 N 个元素数组的整个长度。该程序的复杂度为 O(2N)。O(2N) 减少到 O(N)，但我觉得只需要一个 for 循环而不是两个的实现会使其成为更快的程序（即使单个 for 循环实现为了速度而牺牲了一些功能） ， 例如）。
我的问题：
如果您有一个时间复杂度为 O(2N) 的算法，将其优化为 O(N) 时间复杂度是否会使其速度提高两倍？
换句话说，将 O(2N) 算法优化到 O(N) 是否会带来显着的好处？我想程序的速度会有所增加，或者增加的幅度是否微不足道，以至于不值得付出努力，因为 O(2N) == O(N) ？
optimization big-o time-complexity micro-optimization space-complexity
比方说，我有我的List<T>课。我有很多函数，我必须传递我T类型的单个对象。例如
void add(const T& item)
{
...
}
T如果是某个类或结构就有意义。但是，如果T是字节或整数，则通过引用传递它是没有意义的，甚至是错误的，因为内存指针花费 8 个字节（在 32 位系统上为 4 个字节），即我通过 8 字节大小的指针传递 1 字节大小的数据类型。
所以我决定使用using指令定义参数数据类型。有点儿：
using argType = const T&; requires sizeof(T) > 8
using argType = T; requires sizeof(T) <= 8
但是，显然，这段代码不起作用。您能为我提出其他解决方案吗？
以下程序(以下说明)适用于非常小的列表,但是当列表包含大量项目(1/2万)时,应用程序进入"无响应"状态,并且完成大约需要2.5分钟(非常糟糕)时间).我可能会添加应用程序需要至少(最终)处理1亿个项目的列表.
这是有问题的过程的代码:
public void removeItems(List<long> L, SortedList<long, List<long>> _subLists)
{
foreach (KeyValuePair<long, List<long>> kvp in _subLists)
{
foreach (long duplicate in kvp.Value)
{
int j = L.IndexOf(duplicate);
L.RemoveRange(j,(int)kvp.Key);
}
}
}
L是长值列表._subLists是一个排序列表,其中每个值都是来自L的值列表,开始一些差异的算术级数系列(不相关).与该值关联的键是值包含的序列的长度.
例:
L = {1,2,3,5,6,7,18,20,21} _subLists = {2,<20>} {3,<1,5>}
该过程简单地从L中删除算术级数序列.
只是好奇,哪个更有效率？
这个:
String a = someString + "." + anotherString;
或这个:
String a = someString + '.' + anotherString;
我用一个unsigned char存储8个标志.每个标志代表一个立方体的角落.所以00000001角落1 01000100将是角落3和7等.我当前的解决方案是&1,2,4,8,16,32,64和128的结果,检查结果是否为零并存储角落.就是这样if (result & 1) corners.push_back(1);.我有机会摆脱那个"如果"的陈述吗？我希望我可以通过按位运算符摆脱它,但我想不出任何.
关于为什么我要摆脱if语句的一些背景知识.这个立方体实际上是一个体素,它是网格的一部分,其大小至少为512x512x512.这超过1.34亿体素.我正在对每个体素进行计算(嗯,不完全是,但我不会详细介绍,因为这里不相关),这是很多计算.我需要每帧执行这些计算.每个函数调用的任何速度提升都是微不足道的,这将有助于这些计算量.为了给你一个想法,我的算法(在某些时候)需要确定浮点数是负数,正数还是零(在某些错误内).我在那里有if语句,比检查更大/更小.我用快速浮点数转换为int函数并将其削减了四分之一秒.目前,128x128x128网格中的每个帧需要4秒多一点.
在运行时性能方面,在Java中将int转换为short是多么昂贵？可能有成千上万的这样的铸造,因此我想知道它是否会影响性能.谢谢.
如何判断在迭代中放入两个额外的赋值是否昂贵,或者设置if条件来测试另一个东西？在这里我详细说明.问题是生成并打印Fibonacci序列的前n个项,其中n> = 1.我在C中的工具是:
#include<stdio.h>
void main()
{
int x=0,y=1,output=0,l,n;
printf("Enter the number of terms you need of Fibonacci Sequence ? ");
scanf("%d",&n);
printf("\n");
for (l=1;l<=n;l++)
{
output=output+x;
x=y;
y=output;
printf("%d ",output);
}
}
但是"如何通过计算机解决它"这本书的作者说这是低效的,因为它对生成的单个斐波纳契数使用了两个额外的赋值.他建议:
a=0
b=1
loop:
print a,b
a=a+b
b=a+b
我同意这更有效,因为它始终保持a和b相关,并且一个赋值生成一个数字.但它一次打印或提供两个斐波那契数字.假设问题是生成奇数个术语,我们会做什么？作者建议设置一个测试条件来检查n是否为奇数.通过在每次迭代中添加if测试,我们不会失去减少分配数量的收益吗？
无论是否使用x += 1或建议我都很困惑x = x+1.我知道他们都产生了相同的结果.实际上,使用时x+=1代替是否有任何性能提升x = x+1？它会让我的程序运行得更快吗？
我是否需要将Dart属性缓存到发布抖动的VM中以获得最佳的最佳性能？
如果使用dartpad，缓存会提高性能。
class Piggybank {
List<num> moneys = [];
Piggybank();
save(num amt) {
moneys.add(amt);
}
num get total {
print('counting...');
return moneys.reduce((x, y) => x + y);
}
String get whoAmI {
return total < 10 ? 'poor' : total < 10000 ? 'ok' : 'rich';
}
String get uberWhoAmI {
num _total = total;
return _total < 10 ? 'poor' : _total < 10000 ? 'ok' : 'rich';
}
}
void main() {
var bank = new Piggybank();
new …我有2个（strcpy）函数的源代码，我想知道哪一个更快，性能更高...
unsigned
strcpy(const char * str, char * des) {
register const char * ptr = str;
while ((*des = *str)) {
str++;
des++;
}
return (str - ptr);
}
unsigned
strcpy2(const char * str, char * des) {
register unsigned i = 0;
while ((des[i] = str[i])) i++;
return i;
}
第一个使用str和des地址，第二个使用索引...第一个使用多余的（++），因此在第一眼看来，由于执行了额外的操作（++），第一个功能的性能低于第二个）中的每个字符，但是当我在GCC中使用（-O3）优化时，结果（汇编代码）告诉我其他信息（第一个strcpy具有更高的性能和更少的动作）
strcpy:
movzbl (%rdi), %eax
movb %al, (%rsi)
testb %al, %al
je .L4
movq %rdi, %rax
.L3:
movzbl 1(%rax), %edx
addq $1, %rax
addq $1, %rsi
movb %dl, …