|
It occurs to me that every algorithm is O(n) for some value n, which may be 2m, m!, m^2, or pretty much anything else, so if I have an algorithm that is O(m!^z), I can simply say that n = m!^z and voila! I have reduced my algorithm to O(n). 
Maybe this will bring Luc back in for a look.
|
|
|
|
|
As long as you're cheating like that, you can also add an arbitrary nesting of logarithms.
|
|
|
|
|
Nesting algorithms are for the birds.
|
|
|
|
|
|
I have the feeling that you are confusing simplifying a problem and solving it... 
If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.
--Winston Churchill
|
|
|
|
|
Nah, not really, though I admit that I still don't truly understand Big-O notation.
What got me thinking about this today was the comment:
"If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle"
Now, I'm pretty sure that the first algorithm to come to mind (and the one I implemented) is not O(n) -- I think it's closer to O(n!) (edit: It isn't; it's O(n^2)) -- so I wonder whether they actually know an O(n) algorithm or maybe they don't understand O(n) notation even as well as I.
From there, it was a simple matter to state that every algorithm is O(n).
modified 2-Aug-15 14:31pm.
|
|
|
|
|
PIEBALDconsult wrote: From there, it was a simple matter to state that every algorithm is O(n).
OK.
If you choose the "correct" criterion for measuring the complexity of your problem, then every problem is indeed O(n). For example, in the Travelling Salesman Problem, if you choose "The number of possible paths" as your complexity criterion, then the problem may be seen as O(n).
Most of us would choose "The number of stops on the route" to be a more useful complexity criterion, which makes the solution to the problem of much higher complexity.
If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.
--Winston Churchill
|
|
|
|
|
The maximum subarray thing? Obviously O(n) operations (with n being the size of the array), with Kadane's algorithm. Or O(n2) by just trying everything. O(n!) .. then you're doing something weird.
I don't know wtf they're talking about with their divide and conquer, it doesn't get any better than Kadane's.
|
|
|
|
|
harold aptroot wrote: The maximum subarray thing?
Yes, shhhh... I didn't want to make this a programming discussion.
Thanks for pointing me to Kadane's algorithm -- I didn't know about it and I see that it is indeed O(n). My implementation is ummm... not. 
But then, the OP was given a more complex problem to solve anyway.
So I didn't get to O(n), but I got some good exercise in C and that's what I wanted.
And I implemented the "larger" problem of being able to tell you exactly which members of the array are involved in the greatest (and longest) subarray sum.
I don't think it's O(n^2) and I suppose I shouldn't have said O(n!). I think it's more like O(1+2+...n), but there's no name for that is there?
I'll continue to think about it and maybe there is an actual O(n) algorithm for this.
harold aptroot wrote: wtf they're talking about with their divide and conquer
I suspect that a shark has been jumped. The code complexity would far outweigh the problem complexity.
|
|
|
|
|
PIEBALDconsult wrote: I think it's more like O(1+2+...n), but there's no name for that is there?
You're absolutely right it would be that funny sum. But actually.. that would be O(n2)
Follows from the old "sum of 1 to n = n(n+1)/2" thing, and n(n+1)/2 is less than 2n2 for all n>0 so it's in O(n2)
edit: actually wait, I'm starting to doubt it would be that sum in the first place. No matter though, enumerating all the subarrays is going to be O(n2) anyway.
|
|
|
|
|
I can see that, thanks.
So the algorithm I implemented is O(n<sup>2</sup>) (at worst) and I added some improvement that should usually reduce the actual effort required.
|
|
|
|
|
harold aptroot wrote: I'm starting to doubt it would be that sum in the first place
Hope I didn't ruin your Sunday.
|
|
|
|
|
That's what she said.
|
|
|
|
|
I'm a C#/WPF guy, and every single one of my classes is coded as follows:
I use regions, and I have the following regions always in this order (assuming there's code there for it):
Constants
Event Declarations
Private Fields
Properties
Dependency Properties
Commands
CTOR
Public Methods
Method Overloads
Private Methods
Event Handlers
In each one of these sections, the items are always in alphabetical order. Why? because when you come in after me and open one of my classes, knowing I code this way, you'll always know where the piece you're looking for is.
I never put code in an event handler, except a call to a private method. Why? Assume you have a bunch of code in a ListBox SelectedItem event. Then you change ListBox to a ComboBox... now you have a bunch of code to do. For a button click.. you're almost certainly going to do multiple things, and all that code doesn't belong in MyButton_Click.
I always correct spelling errors. Why? because I'm not lazy and leaving it is just wrong.
I always use XAML comments. Why? So when you use my class you'll know what things do.
I always comment where appropriate, and I always keep comments current. Why? You already know why.
When a class is finished, I always remove and sort namespace usings. Why? Less code is better.
Now this is just me... I'm anal like this. What about you? I'm curious how other people code.
If it's not broken, fix it until it is
|
|
|
|
|
Yes.
Kevin Marois wrote: XAML comments
Kevin Marois wrote: Less code is better.
Sure, but that doesn't mean "fewer keystrokes" is better (some practitioners (even language designers) don't seem to understand that). A statement should be as informative to the reader as possible. You only write it once, but it's read many times, so don't be lazy up front.
modified 1-Aug-15 20:58pm.
|
|
|
|
|
I simply meant that I remove unused code. If a namespace is inserted, then not used, remove it.
Same with commented out code. If it's truly deprecated, the remove it.
If it's not broken, fix it until it is
|
|
|
|
|
Kevin Marois wrote: Same with commented out code. If it's truly deprecated, the remove it.
Right on! Besides, you can always get that code back since you're using a Version Control System.
Uh... you are using a VCS, right? Rrrrr...iiight? 
I'm sure you are, OP. It's the others who leave their deadwood code in that I don't trust. 
|
|
|
|
|
+1 Kevin for removing commented out code
We can’t stop here, this is bat country - Hunter S Thompson RIP
|
|
|
|
|
Agreed 100%. 
I view my source code as a representation of myself. I would hate to have another developer scratch their head to figure out what my code does. My choice of #region ordering is slightly different, but it's the same in principle.
/ravi
|
|
|
|
|
Some people can't stand regions.. I don't understand that at all. Why in the world would I want to keep looking at dozens or hundreds of lines of code I don't need to see.
If it's not broken, fix it until it is
|
|
|
|
|
Kevin Marois wrote: Why in the world would I want to keep looking at dozens or hundreds of lines of code I don't need to see.
Exactly. I find code folding to be a helpful editor feature. I also use it in Android Studio (which supports //region and //endregion tags).
/ravi
|
|
|
|
|
I use regions occasionally. What I don't like (in C#) is that regions appear as compiler directives when they actually have no affect on the compiler, only on some (not all) text editors. But that doesn't keep me from using them when appropriate.
And I think defining regions based on purpose, rather than type is likely to provide greater value to the reader.
I prefer to split classes up into smaller files as appropriate -- to separate large chunks, such as features and whatnot. Huge monolithic class files are a poor design choice (and was flabbergasted when I found that C# v1 enforced it!) in my opinion. It is to be hoped that smaller files make working with a code management system simpler -- less branching and merging as there should be less need for multiple developers to work on the same file at the same time for instance. I don't care how good your merge engine is, the best merge engine is one you don't need to use.
|
|
|
|
|
If you keep your classes small, then the Region declarations just become noise. Smaller classes are better at hiding the hundreds of lines of code you don't need to see as well.
|
|
|
|
|
Amen! There must a correlation between lines of code per abstraction and the likelihood of heart failure in the near future.
|
|
|
|
|
Kevin Marois wrote: Some people can't stand regions
I added the "Collapse to Definition" button to the toolbar, this collapses my VM code to Properties and Methods, I use nested regions - a LOT 
Never underestimate the power of human stupidity
RAH
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
