blocks|key|5311895|text|如果您需要对一组n元素中的每个元素执行某些操作，则无法获得高于O(n)的性能。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|5311896|entityMap^0|8|1|X|1|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|M|8|@]|D|@]|E|$]]]|G|$]]

If you need to do something to each element of a set of <code>n</code> elements, you cannot do it with better than O(<code>n</code>) performance.

blocks|key|3200942|text|如果你的意思是“在一个独立于N的时间内初始化一个由N个项目组成的密集数组”，那么这在物理上是不可能的。密集数组的存储空间与项的数量呈线性增长，初始化该空间需要线性的时间。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3200943|您可以使用稀疏数组进行固定时间的初始化。这本质上是一个关联数组(或hashmap，或字典，或表，取决于语言)，它在项目第一次被访问时对其进行初始化。|3200944|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

If you mean "initialize a dense array of N items in a time independent of N", then it is physically impossible. A dense array has a storage space that grows linearly with the number of items, and it will take a linear amount of time to initialize this space.

You can have constant-time initialization using a sparse array. That is essentially an associative array (or hashmap, or dictionary, or table, depending on the language) which initializes items when they are first accessed.

blocks|key|3200961|text|我认为这只是一个简单的语法问题。在C%2B%2B中，您可以执行以下操作：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3200962|int+foo[1000]+=+{0};|code-block|syntax|javascript|3200963|数组中的所有值现在都是0|3200964|虽然它看起来像是在固定时间内完成的，但它仍然是O(n)|3200965|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|P|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

I think its just a simple syntax question. In C++ you can do this:

<pre><code>int foo[1000] = {0};
</code></pre>

All values in array are now 0

While it looks like its done in constant time, it still O(n)

blocks|key|2214751|text|实际上，这是可能的，但只有在硬件的帮助下。在软件上，您必须执行许多与n成正比的步骤，因此它是O(n)；然而，在硬件上，您可以进行连接，以便并行设置数组的所有元素。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|2214752|这实际上是时间/空间的折衷；以前需要O(n)时间，现在需要O(n)电路元件，但可以在O(1)时间进行操作。|2214753|这实际上是一件很常见的事情。许多硬件都有一个复位输入，当它被断言时，会将整个硬件设置到一个已知的状态。例如，这可以涉及将整个存储器归零。|2214754|entityMap^0|Y|1|1A|4|0|I|4|T|4|16|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@$9|M|A|N|B|C]|$9|O|A|P|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|Q|8|@$9|R|A|S|B|C]|$9|T|A|U|B|C]|$9|V|A|W|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|X|8|@]|D|@]|E|$]]|$1|J|3|-4|5|6|7|Y|8|@]|D|@]|E|$]]]|K|$]]

Actually, it is possible, but only with hardware help. On software, you will have to do a number of steps proportional to <code>n</code>, thus it is <code>O(n)</code>; on hardware, however, you can wire things so that all elements of the array are set in parallel.

This is in fact a time/space tradeoff; while before one needed <code>O(n)</code> time, now one needs <code>O(n)</code> circuit elements but can do the operation in <code>O(1)</code> time.

And it is actually a common thing to do. A lot of hardware has a reset input which, when asserted, sets the whole hardware to a known state. This can involve for instance zeroing the whole memory.

blocks|key|3201094|text|如果您在所有未来的操作中使用Amortized+Analysis来计算运行时，那么您可以在O(1)中使用+do。你只需要按需初始化你的元素(第一次读取时)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|BOLD|entityRanges|data|3201095|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Amortized_analysis^0|9|17|E|I|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]]|D|@$9|Q|A|R|1|S]]|E|$]]|$1|F|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]]]

You can do it in O(1), if you calculate the runtime with an <a href="http://en.wikipedia.org/wiki/Amortized_analysis" rel="nofollow">Amortized Analysis</a> over all future read actions. You just have to initialize your element on demand (the first time its read).

blocks|key|2221019|text|您可以在O(1)时间内使用常量值初始化数组。但它需要额外的内存。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2221020|看一看Initializing+an+array+in+constant+time|offset|length|2221021|entityMap|0|LINK|mutability|MUTABLE|url|https://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time^0|0|3|12|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

you can initialize an array with a constant value in O(1) time. but it requires extra memory.

have a look at <a href="https://eli.thegreenplace.net/2008/08/23/initializing-an-array-in-constant-time" rel="nofollow noreferrer">Initializing an array in constant time</a>

blocks|key|3201125|text|这是可以做到的！|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3201126|您可以使用O(1)最坏时间和O(1)额外空间来初始化一个数组，并且可以将其改进为仅使用1个额外的内存。|offset|length|style|BOLD|3201127|这两个都可以在这个中找到，在这个中简单地解释，并在项目中实现。|3201128|完全公开--最后两篇是我写的。|3201129|它是state-of-the-art可初始化的数组，并且可能会一直保持这个数组。上面的论文证明了，即使对于分期/随机化算法，如果没有额外的位填充(init)操作，也应该占用Ө(n)时间。|3201130|entityMap^0|0|17|5|0|0|0|2|G|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@$D|R|E|S|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@$D|W|E|X|F|G]]|9|@]|A|$]]|$1|N|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|O|$]]

<h1>It can be Done!</h1>
You can initialize an array in O(1) worst-time and O(1) extra space, and it can be improved to using only 1 extra bit of memory.
Both can be found in this <a href="https://arxiv.org/abs/1709.08900" rel="nofollow noreferrer">Paper</a>, explained simply in this <a href="https://link.medium.com/Q8YbkDJX2bb" rel="nofollow noreferrer">Article</a>, and implemented in the <a href="https://github.com/tomhea/farray" rel="nofollow noreferrer">Farray</a> project. 
Full disclosure - the last two were written by me.
It is the state-of-the-art Initializable array, and will probably stay that. The above paper proves that without the extra bit - the fill (init) operation should take Ө(n) time, even for amortized/randomized algorithms.

blocks|key|308312|text|不是的。这在物理上是不可能的。但是，您可以使用向量指令使其达到O(n+*+1/k)时间，其中k是向量设置器指令的宽度。这仍然是O(n)，但常量缩小了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|308313|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

No. It's physically impossible. However, you can use vector instructions to make it some O(n * 1/k) time, where k is the width of a vector setter instruction. That's still O(n), but the constant is shrunk.

someone has an idea how can I do that ?

thanks

initializing an n elements array using O(1) performence?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

问使用O(1)性能初始化n元素数组？
EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问使用O(1)性能初始化n元素数组？EN

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问使用O(1)性能初始化n元素数组？
EN