Source: wikimedia.org |
Let's compare asymptotic time complexity of two following loops:
int[] _array = Enumerable.Range(0, n).ToArray(); List<int> _list = Enumerable.Range(0, n).ToList(); //ListChangeByIndex for (var i = 0; i < n; i++) { _list[i] = i + 1; } //ArrayChangeByIndex for (var i = 0; i < n; i++) { _array[i] = i + 1; }How do you think, which one is faster?
.
.
.
.
Many developers think the fist one will be slower, because in each loop computer is forced to visit all nodes from 0 to i to finally set the variable.
.
.
.
.
However, that's not the case. Both loops have O(n) complexity. That's because in the .NET source we can clearly see that's underlying data structure for a List<T> is an array: list.cs. Therefore, those two loops are essentially equal.
I recommend a nice article regarding .NET collections complexity: http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html
ReplyDeleteIndeed a must-read for every .NET pro. Here is another, simillar article: http://www.growingwiththeweb.com/2013/02/what-data-structure-net-collections-use.html
Delete