變量初始化/賦值語句是單個操作還是更多？

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;這樣的事情算作一個操作或兩個「基本上是一個慣例。