/sci/ - Science & Math » Thread #11468528

293KiB, 900x598, ZEmZ6.png

View Same Google iqdb SauceNAO

Anonymous Sat 14 Mar 12:24:28 2020 No.11468528 View Reply Original Report

Quoted By: >>11468594 >>11468639 >>11468658 >>11469113 >>11470611 >>11470918

Is there a way/term to distinguish between complexity that is due to the complexity of the operations involved and complexity that is due to the amount of operations involved?

For example, computing an integral is more complex that computing 2 + 2 (complexity of operations)
And having to do ten millions additions is more complex that computing 2 + 2 (amount of operations)

I know this isn't exactly CS-type complexity theory, I just wonder if there is a term to describe each.

Anonymous

Anonymous Sat 14 Mar 2020 13:03:14 No.11468594 Report

Quoted By: >>11468599

>>11468528
Don't know if theres a specific term for each. But at the end of the day complex operations turn into high amount of operations problems because we have to use brute-force + heuristics to solve it, because we don't know better. Then those tend to involve higher than polynomial amount of operations, i.e exponential/factorial in your chart.
Theres probably a class of problems that are sufficiently "humanly complex", but we still know them pretty well to solve in polynomial time, but again I don't know if theres a specific term for it, we just call them complex I dunno.

Anonymous

Anonymous Sat 14 Mar 2020 13:05:20 No.11468599 Report

Quoted By:

>>11468594
yeah that's why I figured it doesn't make sense from a CS perspective, because in the end you're just reducing the problem to a series of basic operations so it's always just about volume.
but looking at it from a human perspective would be different

Anonymous

Anonymous Sat 14 Mar 2020 13:34:35 No.11468639 Report

Quoted By:

>>11468528
nlogn really isn't that bad

Anonymous

Anonymous Sat 14 Mar 2020 13:47:17 No.11468658 Report

Quoted By:

>>11468528
There's no term, but each complex operation is a combination of simpler operations. The best way is by thinking of multiplication.
Multiplication is just adding a number by some specific no of times. Ex 3*8 means to add 8, 3 times or 3, 8 times.
Hence the same applies in complexity too.
Ex say an addition takes O(1)
Now what if we have N such numbers in an array and want to add all. We perform the add operation, O(1), N times i.e. O(N*1)=O(N)
There's no term but this is just the way math for complexity checks out.

Anonymous

Anonymous Sat 14 Mar 2020 17:20:32 No.11469113 Report

Quoted By: >>11470143

>>11468528
This image makes me seethe because it's saying that nlogn algorithms are bad even though the best sorting algorithms are nlogn. Don't get me started on calling O(n^2) a terrible complexity...

Anonymous

Anonymous Sat 14 Mar 2020 23:45:21 No.11470143 Report

Quoted By:

>>11469113
also doesn't take into account average case complexity or space complexity, e.g. why counting sort is actually shit in practice

Anonymous

Anonymous Sun 15 Mar 2020 02:13:04 No.11470611 Report

Quoted By: >>11470651

>>11468528
>n^2 and n! are in the same category of terrible
This is so retarded it hurts. The difference makes n log n basically look like it's linear.
O(1) is pretty much a non-algorithm and not even worth indexing.
Shift everything down to its lower neighbour and this chart is perfect.

Anonymous

Anonymous Sun 15 Mar 2020 02:29:56 No.11470644 Report

Quoted By:

Complexity doesn't have to do with how much time the computation of a function takes, but how it scales up, but I understand your point. Kolmogorov complexity would give you what you want, but by definition it should be minimal, and that's not the case of your problem.

Anonymous

Anonymous Sun 15 Mar 2020 02:32:54 No.11470651 Report

Quoted By: >>11470873 >>11470918

>>11470611
Shut the fuck up, x! and n^2 are both babby tier.

Anonymous

Anonymous Sun 15 Mar 2020 04:14:08 No.11470873 Report

Quoted By:

>>11470651
n^2 is a pretty common complexity and not catastrophically bad.
Any doubling in scope just increases the complexity by four times. Not the end of the world.

Anonymous

Anonymous Sun 15 Mar 2020 04:34:17 No.11470918 Report

Quoted By:

>>11468528
We generally address the modularity of our complexity analysis based on what operations we take at 'unit cost.' If you want to give a more informatic flavor to some lower bounds, you could talk about Kolmogorov complexity...but nothing there is particularly well studied / tight.
>>11470651
n^2 is so much better than n! it's not even funny. We're generally okay with our hardest practical shit being n^2 as long as we have lookup be linear or even constant.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches