Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Putnam]

An algorithm is O(n) if its run time grows linearly with n, which usually means the size of the input. For example, looping through an entire array uninterrupted is trivially O(n).

An algorithm is O(log n) if its runtime grows logarithmically with n. For example, searching through a sorted array with a binary search is trivially O(log n); an array of 256 size will take a mere 8 steps at most to find the part you want.

Big-O notation is a general way to say how something's runtime increases with the size of the input. It should be noted especially that this is asymptotic: O(n) is still O(n) even if the actual amount of steps taken is 1,000,000,000*n, as that is still a linear growth profile.

[Reelya]

Yeah, that's where knowing more about your problem domain / size of n is really helpful to optimize further. e.g. you might pick an implementation because it's "O(log n)" instead of "O(n)" or even "O(n^2)", but for small values of n, and/or if the log-n operations are very costly, then you might have chosen wrong.

e.g. "finding the smallest" in a heap is O(log n), but finding the smallest in a sorted list is O(1), or a constant amount of time no matter how many elements there are. So whether to use one or the other would depend on the cost / frequency of that operation vs other operations.

[da_nang]

To be specific, in most programming contexts O(f(n)) means f(n) is the asymptotic upper bound, Ω(f(n)) means f(n) is the asymptotic lower bound, and Θ(f(n)) means f(n) is the asymptotic lower and upper bound. There are also small-o notation but I haven't seen it used in Comp Sci.

If g(n) = O(n) then g(n) = O(n²) holds as well.

O(f(n)) is what most programmers care about unless you're really into optimization analysis, in which case I've seen Θ(f(n)) be used.

[Reelya]

Humble Bundle of Game Dev software:
https://www.humblebundle.com/game-developer-software-bundle

[Shadowlord]

If you're familiar with the costs of low level operations and (I guess we could call it advanced) optimization from studying processor reference guides, it becomes apparent that big-O notation and other simplifications are not everything. (An addition is over 60 times as fast as a multiplication, for instance, square roots are exceedingly slow, and you can make code run faster by rewriting/rearranging your if statements so that the most likely conditions are first)

That said, there's no point in taking a lot of time to optimize something which isn't a bottleneck.

[DragonDePlatino]

What do o(n) and o(log n) mean? Now that it's relevant to a current project, I might have enough context to get it.

In easier to understand terms, Big-O notation is "how many steps do I need to do something". This first example is a constant algorithm, or O(1). No matter how big the list is, it will always take 1 step to print the first index. These are the fastest possible algorithms.

Code: [Select]

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(list[0])
A little slower than that is a logarithmic algorithm, or O(log n). That is when you want to do something, but it becomes expontentially faster the more stuff you want to do. The following is a logarithmic algorithm. Every step, the index i is doubled and then printed out. Doing this for 10 numbers would take 4 steps. 100 numbers would take 7 steps. 1,000,000,000 would take 29. In most situations, O(log n) is the best you can get.

Code: [Select]

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
i = 1
while i < len(list):
print(list[i])
i = i * 2
Next there are O(n) algorithms, or linear algorithms. For every piece of data I have, I need to perform one step. The number of steps grows linearly compared to the amount of data I have. This is a linear algorithm:

Code: [Select]

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i in list:
print(i)
Even slower than that are O(n log n) algorithms. As you might've guessed, these are as slow as O(n) and O(log n) combined. Generally speaking, you have one loop that is O(n) and another that is O(log n). This algorithm looks at every index in my list, then multiplies it by index 1, 2, 4, 8, 16...

Code: [Select]

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for n in list:
i = 1
while i < len(list):
print(n * i)
i = i * 2
Lastly are quadratic O(n^2) algorithms. There are even slower algorithms than these, but they are less common. A quadratic algorithm becomes exponentially slower the more stuff you want to do. They're like the opposite of logarithmic algorithms. In this example, I multiply every index by every other index. 10 numbers would take 100 steps. 100 numbers would take 100,000 steps. 1,000,000,000 would take 1,000,000,000,000,000,000 steps. Obviously, these are terrible algorithms.

Code: [Select]

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for n in list:
for n in list:
print(n * n)
This is an extreme simplification and I know people will chew me out for it, but as someone who just learned this stuff I know technical jargon can mask understanding.

[Reelya]

That said, there's no point in taking a lot of time to optimize something which isn't a bottleneck.

Yeah, that's why the best optimizations to learn are the rules of thumb about how you originally design your data/logic flow. Because you get a lot of bang for your buck and it's more about designing with efficiency in mind rather than going back to "optimize" sloppy code later:

- put most likely branches first in if statements
- go with the grain of memory for 2D array reading
- order data from big to small in structs/classes
- keep total structs <= 64 bytes. powers of 2 for struct size are extra-efficient
- don't interleave data that gets checked frequently. e.g. if you have key=>value search, store the keys and values in separate arrays.

These things are easy to do, and are things the compiler either cannot reason about or is prevented from changing by itself. One that Mike Acton mentions, but is a bit trickier so should only be implemented for bulk data is that if you "vectorize" functions that are performed on many small objects, you can massively speed up processing of the objects. The trick is to look at how much data is being passed into the processing function per call. if it's e.g. 8 bytes of data, then you can pack 8 items worth of processing into a 64-byte chunk of memory (or design things so that it's already packed), then make a version of the function that takes a pointer and processes 8 items at a time. The times to look out for these opportunities is when you have a for loop, in which the only thing happening is calling a function.

[Putnam]

-snip-

O(1) isn't necessarily one step, it's just constant with the size of the input.

[i2amroy]

There are also small-o notation but I haven't seen it used in Comp Sci.

Yeah my algorithms class basically said "here's these things, they exist, nobody ever uses them except math people working on 'proving' specific algorithm stuff".

[itisnotlogical]

Something I learned today: C# lists generate garbage like nobody's business if you create them without some default capacity, specifically calls to List.GrowIfNeeded when you add a lot of things. Went from 2 kilobytes going on the heap per agent, to 0 except where the path is really twisty and encompasses hundreds of nodes.

I used to be afraid of trying to optimize things, but I'm finding it's really fun to hunt down bottlenecks and steadily beat the numbers down to nothing.

[eerr]

Code: [Select]

list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
i = 1
while i < len(list):
print(list[i])
i = i * 2Alright so I don't understand how this example provided is O(log n)

[eerr]

Oh, I never considered multiplying an iterator. I guess it's the base case where you don't actually do anything special with it!
I do know that has practical applications for a database or other data access.

[monkey]

Code: [Select]

void sortedInsert(Path_GraphNode node)
{
for(int i = 0; i < openList.Count; i++)
{
if(node.f > openList[i].f)
{
continue;
}
openList.Insert(i, node);
return;
}
}

Does it perform better than with an unordered list ?

List.Insert is also O(n): https://msdn.microsoft.com/en-us/library/sey5k5z4(v=vs.110).aspx
It's backed by an array, when you Insert at the head of the list, it has to shift every other object 1 position to the right to make room.
And in A* that is probably what happens all the time, hopefully.

You could try with LinkedList, LinkedList.Insert is O(1): https://msdn.microsoft.com/en-us/library/he2s3bh7(v=vs.110).aspx
Or better, with a binary_heap as someone mentioned.

[itisnotlogical]

With an unordered list I'd have to potentially search the entire list for the lowest F score, depending on what kind of luck I have with where A* decides to search in certain scenarios (especially in the case of ties). OTOH, I'm hopefully saving time with my method, since A* pursues the lowest F-score which means nodes will be inserted after only partially going over the list. I tried implementing a binary search but I couldn't figure it out, I ended up with wonky paths and no better performance.

Thanks for the tip about LinkedList.Insert being O(1) though. I'll try that sometime today and post about it.

I still feel like I could shave off the last few milliseconds to get what I'd consider acceptable performance, without writing a binary heap that'd also need to be tested and rewritten and put into the existing stuff.

[Shadowlord]

Fair warning: Linked lists tend to be really good at clobbering your CPU with cache misses, which slows things down massively if they occur. (Yet another reason why big-O notation can mislead you into making suboptimal choices )

CPU caches can mitigate it, if you don't have a lot of data in the program's memory, but when you've got enough stuff in the program's memory, then your linked lists will likely start generating cache misses, slowing down anything you do with said linked lists.