变量初始化/赋值语句是单个操作还是更多？

Question

我刚刚学习算法的性能分析

我的问题：是int i=0;被算作两个操作：assisgment，intialization或者它只是一个紧凑操作？ 我正在使用渐近分析，它使用no操作作为如何描述性能的示例

Answer 1

没有一个正确的答案。

在某些情况下，人们可能会将单个算术操作分析为“一个”操作。其他时候，他们可能会精确地关心一次手术需要多少次循环，他们可能会说，例如，增加ints比浮点数乘以便宜。

在许多情况下，程序员说，解引用指针O(1)。然而，如果你真的在考虑这种情况，当n变为无穷大时，如果你的n就像宇宙的大小一样，说取消引用一个指针为O(1)的操作是否有意义？ In some theoretical contexts，人们会说本质上取消引用指针是O(log n)。然而，我曾与一位物理学家交谈过，他曾经说过，即使O(log n)可能不是物理上的现实 - 他说宇宙在给定的体积空间中可以有最大的信息密度。这被称为“Bekenstein Bound”，事实证明最大熵是通过黑洞实现的。如果你假设在一个空间体积n中你只能有O(n)位内存，它基本上意味着在一个星系大小的计算机中，位必须像sphere packing problem中的球那样打包，然后在一个典型的一对位正在增长为O(n^{1/3})。由于信息的速度并不比光速快...可能解引用指针需要O(n^{1/3})渐近？ O.o

要点是，不要过时这一点。你在渐近分析中做的任何事情最终都是一个近似值，你只是试图获得一个有用的想法，它需要多长时间。你很确定的事情在你的案例中并不重要，你可以分析为O(1)，以便专注于重要的事情。在另一种情况下，如果它们代表了“最”的工作，那么您可能想要分析的内容也会有所不同。

IMO如果你想知道如何在面试中回答关于这个问题的问题，你应该准备好以多种不同的方式分析它，并告诉他们你明白像“int i = 0;这样的事情算作一个操作或两个“基本上是一个惯例。