タイトルが尋ねるように、LinkedListクラスのsize()メソッドが償却されたO(1)時間かO(n)時間かかりますか?JavaのLinkedListでsize()呼び出しの時間の複雑さはどのくらいですか?
答えて
それは(Oです1)。あなたは、ソースコードのためのgoogleすることができますし、そのように来る:http://www.docjar.com/html/api/java/util/LinkedList.java.html
から
私は変数としてサイズの店で見てきたコレクションクラスのすべてをし、それを得るためにすべてを反復処理していません。
NetBeansでCtrlキーを押しながらクリックすると、Googleよりも高速に検索されます。 – Superole
のLinkedListからO(1)あなたがソースコードを見ていたあなたが発見したと同じように...
:
private transient int size = 0;
...
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
Sunの実装をまったく使用していないのであれば? http://en.wikipedia.org/wiki/Java_Class_Library#Alternative_implementations 私は彼の質問は、特定の実装/バージョンでO(1)であるかどうかではなく、O(1)であることが保証されているかどうかということです。 – jalf
LinkedListが導入されたときの実装は1.2以降であるため、常にO(1) –
になります。これはJava 1.6からのものです。これはVMに依存しませんが、(理論上の)旧バージョンの標準ライブラリでは異なる可能性があります。あなたが100%確実であることを望むならば、あなたのバージョンのソースをチェックしてください。しかし、正気な開発者は、すべてがメモリ内にあるこのようなもののサイズを計算し、構造が作成されるとそれを集計することはできません。 – Kris
- 1. javaのlastIndexOfの時間複雑度はどのくらいですか?
- 2. クイックユニオンの時間複雑度はどのくらいですか?
- 3. Pythonでzip()の時間の複雑さはどのくらいですか?
- 4. JavaScriptのparseInt()の時間の複雑さはどのくらいですか?
- 5. 次の式の時間の複雑さはどのくらいですか?
- 6. ツリートラバーサルの時間の複雑さはどのくらいですか?
- 7. heapifyUp()メソッドの時間の複雑さはどのくらいですか?
- 8. サーバループでの呼び出し時間(NULL)はどれくらいですか?
- 9. yieldからのツリートラバーサルの時間複雑度はどのくらいですか?
- 10. 時分割ソートアルゴリズムの時間複雑度はどのくらいですか?
- 11. Neo4jの検索クエリの時間複雑度はどのくらいですか?
- 12. このアルゴリズム(コード)の時間複雑度はどのくらいですか?
- 13. 次のコードの時間的複雑度はどのくらいですか?
- 14. このプログラムフラグメントの時間複雑度はどのくらいですか?
- 15. この関数の時間複雑度はどのくらいですか?
- 16. このdo-whileループの時間複雑度はどのくらいですか?
- 17. この関数の時間複雑度はどのくらいですか?
- 18. この擬似コードの時間複雑度はどのくらいですか?
- 19. アルゴリズム全体の時間複雑度はどのくらいですか?
- 20. 暗号ハッシュ関数の時間複雑度はどのくらいですか?
- 21. クイックソートの平均的な時間複雑度はどのくらいですか?
- 22. JavaでのStringBuilder.append()の複雑さはどのくらいですか?
- 23. AngularJSディレクティブは、一度に呼び出すのではなく、複数の時間を呼び出します。
- 24. どこでJavaメソッドの時間複雑さを見つけるのですか?
- 25. 時間の複雑さ(Java、Quicksort)
- 26. 私のソリューションの複雑さはどのくらいですか?
- 27. Javaで時間の複雑さが設定されている
- 28. JavaのTreeSet部分ビューのsize()の複雑さは何ですか?
- 29. 再帰アルゴリズムの時間複雑さと空間の複雑さはどのようなものですか?オペレーター?
- 30. 時間の複雑さは
並列構造の計算では、サイズが遅く、とにかく無意味です。 –