相关疑难解决方法(0)

在任何情况下,您是否更喜欢O(log n)时间复杂度和O(1)时间复杂度？或O(n)到O(log n)？

你有什么例子吗？

我听说在C++动态内存分配的上下文中使用了几次"内存碎片"这个术语.我发现了一些关于如何处理内存碎片的问题,但找不到直接处理它本身的问题.所以:

• 什么是内存碎片？
• 如何判断内存碎片是否对我的应用程序有问题？什么样的计划最容易受到影响？
• 处理内存碎片的常用方法有哪些？

也:

• 我听说使用动态分配可以增加内存碎片.这是真的？在C++的上下文中,我理解所有标准容器(std :: string,std :: vector等)都使用动态内存分配.如果在整个程序中使用它们(特别是std :: string),内存碎片更可能是一个问题吗？
• 如何在STL繁重的应用程序中处理内存碎片？

也许从平台到平台不同,但是

当我使用gcc编译并运行下面的代码时,我每次都在ubuntu 11.10中得到0.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    double *a = (double*) malloc(sizeof(double)*100)
    printf("%f", *a);
}

为什么malloc表现得像这样,即使有calloc？

是不是意味着只是将值初始化为0会产生不必要的性能开销,即使您有时不想要它也是如此？

编辑:哦,我之前的例子不是initiazling,但碰巧使用"新鲜"块.

我正在寻找的是为什么它在分配一个大块时初始化它:

int main()
{
    int *a = (int*) malloc(sizeof(int)*200000);
    a[10] = 3;
    printf("%d", *(a+10));

    free(a);

    a = (double*) malloc(sizeof(double)*200000);
    printf("%d", *(a+10));
}

OUTPUT: 3
        0 (initialized)

但感谢您指出在进行mallocing时存在安全原因!(没想过).当分配新块或大块时,它必须初始化为零.

假设我有两种算法:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

这很自然O(n^2).假设我也有:

for (int i = 0; i < 100; i++) {
  for (int j = 0; j < n; j++) {
    //do something in constant time
  }
}

这是 O(n) + O(n) + O(n) + O(n) + ... O(n) + = O(n)

似乎即使我的第二个算法是O(n),它也需要更长的时间.有人可以扩展吗？我提出它是因为我经常看到算法,例如,他们将首先执行排序步骤或类似的事情,并且在确定总复杂度时,它只是限制算法的最复杂元素.

使用new,malloc等动态内存分配的时间复杂度是多少？我对内存分配器的实现方式知之甚少,但我认为答案是它取决于实现.因此,请回答一些更常见的案例/实施.

编辑:我依稀记得在最坏的情况下听到堆分配是无限的,但我真的对平均/典型情况感兴趣.