Re: Where is NSList?
Re: Where is NSList?
- Subject: Re: Where is NSList?
- From: Ken Ferry <email@hidden>
- Date: Thu, 29 Jul 2004 16:14:36 -0400
f(n) is O(g(n)) if there exists an N and a k such that for all n > N,
f(n) < k*g(n).
When we say 'an algorithm is O(g(n))', what we mean is that f(x) is
O(g(n)) where f(x) gives the maximal possible 'time' to complete
running the algorithm for an input of 'size' x.
f(n) is Theta(g(n)) if f is O(g) and g is O(f).
Further general cs should probably be off-list.. don't want to spam up boxes.
-Ken
On Thu, 29 Jul 2004 12:45:56 -0600, David Blanton <email@hidden> wrote:
>
I don't claim to be a computer scientist but I can devise awesome data
>
structures algorithms with the best. Now to my question about this thread:
>
>
What is the definition of O(1), O(lg n) and Theta(n).
>
>
(If it helps get an answer I do have a math degree from Berkeley so I will
>
understand the definitions.
>
I just don't know the functions O() and Theta() )
>
>
Thanks for the lesson!
>
>
DB
>
>
>
>
>
On 7/29/04 3:17 AM, "Steve Checkoway" <email@hidden> wrote:
>
>
> On Jul 28, 2004, at 2:48 AM, Pandaa wrote:
>
>> I strongly suggest everyone who contributed to this confusion read up
>
>> on basic computer science.
>
>
>
> I'm sorry you think I need to brush up on computer science basics (you
>
> are quite wrong). You should not be insulting to people attempting to
>
> help, let alone make assumptions about their programming
>
> ability/knowledge.
>
>
>
>> Ordered and indexed. A list is ordered and non-indexed. An array has
>
>> O(n) insert and remove and O(1) indexed random access. A list has O(1)
>
>> insert and remove and O(n) indexed random access.
>
>
>
> A list has O(1) remove only if you already have a pointer to the node.
>
> In the best case, it is O(1), in the average and worst cases, it is
>
> Theta(n) since you have to first find the element which takes linear
>
> time.
>
>
>
>>> I'd suggest using NSArray/NSMutableArray for ordered collections, and
>
>>> only worrying about their access characteristics if use and profiling
>
>>> of your application point to them as a performance issue.
>
>>
>
>> This is a *very* naive view which may well lead to O(n^2) or worse
>
>> implementations of O(1) problems!
>
>
>
> Programmers are notorious for optimizing the wrong code. The pervious
>
> point was well made and perfectly valid. Don't waste your time
>
> needlessly optimizing this code unless it is actually a bottleneck.
>
> While writing a doubly linked list is fairly simple, why bother if it
>
> doesn't effect the performance of the application appreciably.
>
>
>
>> I happen to have a doubly linked list class laying around, if anyone
>
>> is interested I can polish it a bit and make it available for anyone
>
>> to use. It is such a trivial thing.
>
>
>
> Indeed it is.
>
>
>
>> To get an efficient linked list on a modern computer, it is necessary
>
>> to use either a custom memory manager or make nodes carry a small
>
>> constant number > 1 of objects. A naive implementation will have poor
>
>> iteration performance as every node will probably be on a new cache
>
>> line.
>
>
>
> It is almost never a good idea for application programmers to concern
>
> themselves with cache characteristics. That's the job of a system
>
> programmer. (Systems programming is also one place where a linked list
>
> is very useful to implement an LRU-like page replacement algorithm.)
>
> Cache characteristics are different for each computer.
>
>
>
> On whim, I checked my data structures and algorithms text book. The
>
> index doesn't even mention cache.
>
>
>
> - Steve
>
>
>
> p.s. Sorry for the slow reply, Mail decided that your mail was Junk.
>
> _______________________________________________
>
> cocoa-dev mailing list | email@hidden
>
> Help/Unsubscribe/Archives:
>
> http://www.lists.apple.com/mailman/listinfo/cocoa-dev
>
> Do not post admin requests to the list. They will be ignored.
>
_______________________________________________
>
cocoa-dev mailing list | email@hidden
>
Help/Unsubscribe/Archives: http://www.lists.apple.com/mailman/listinfo/cocoa-dev
>
Do not post admin requests to the list. They will be ignored.
_______________________________________________
cocoa-dev mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/cocoa-dev
Do not post admin requests to the list. They will be ignored.