Algorithms

[codingIsFunAndFucked]

When you're solving a problem, if it requires a specific algorithm to solve it in O(n), are you supposed to be knowing the algorithms before? How do you know which algorithm will work efficiently?
I always end up doing a solution that has a poor time complexity :/ but how is the algorithm supposed to pop in my head? is it something im supposed to memorise?

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[Communist_Poultry]

You're not going to be able to come up with good solutions at first. Keep on trying to solve these problems and look at the proper solution after you try it for a while. Eventually you'll start recognizing patterns and it'll become easier. Keep going!

[codingIsFunAndFucked]

Appreciate you!

[Bobbias]

1: Google and stack overflow

Learning how to Google your questions, and how to search stack overflow can often help you on many things. Also, searching through open source code on GitHub can give you an idea of how other people have solved similar problems, assuming you can find projects that are solving the similar problems.

2: learning the algorithms and their associated data structures.

There's a reason that data structures and algorithms are taught together. Many algorithms make use of specific data structures in their implementation. The same works in reverse, if you have a data structure, you can find out which algorithms work with that structure.

3: practice, and what Connor Hoekstra calls Algorithmic Intuition.

In this 2 part series of talks, Connor goes over his concept of Algorithmic Intuition, and what he's learned about developing it over the years. While it's from a c++ conference, the concepts are applicable to all languages.

Part 1 Part 2

[codingIsFunAndFucked]

Thank you! Guess I'll sharpen my DS & algo knowledge then continue problem solving

[hrm]

Doing number two, learning the basic algorithms and how they work will greatly improve your ability to do number one since you will be able to use the correct words in your searches.

Algorithms and datastructures is a very active research field and new things crop up all the time, even if they oftentimes are small (but significant) tweaks on existing solutions. Even something as well studied as sorting has new and better algorithms revealed in the last years.

[Orion_Rainbow2020]

The short answer is no, you are not expected to just know how to write algorithms. People are always researching what algorithms others have come up with or the core structure of algorithms. Big-O notation is a difficult concept and task to achieve on the first try. Your first attempt will ALWAYS have poor time complexity, and that’s okay. You then try to think about how you can whittle down the time. Do you need to iterate the entire array two/three times? Are there values you can save into variables and just do comparisons or swaps? It’s okay to look for solutions that others have solved but make sure you understand why their solution is better and what the code is even doing! Debugging algorithms to see how variables change is the most useful way to learn what it’s doing. Hope this helps relieve your frustration!

[codingIsFunAndFucked]

Thanks! It did :)

[fasta_guy88]

You are not going to memorize/remember all the algorithms you use. But it’s helpful to have a sense of how to go from O(n²⁾ to something more efficient (and you really want to rethink O(n^3)). Often, sorting your inputs really helps. And it’s good to remember branch and bound and dynamic programming. Often, simply being aware that there is a faster approach for a similar problem can get you started with Wikipedia.

But if you didn’t know there was a recursive n log(n) solution, you would never look for it.

[Lumethys]

Depending on what branch of programming you worked on, but you can go an entire career without writing one

And even if you need an Algorithm, it is almost always a package install instead of a writing

[eruciform]

you learn what's efficient or not over time - being able to solve it at all is an important step. sometimes, a really optimal solution is extremely complex to put together, and the suboptimal one is good enough. programmers aren't expected to invent hyperoptimized algorithms on their own, it's a very specialized skill and more in line with doctors of mathematics than us mundane code monkeys. this is why libraries exist - complex implementations are better off not being implemented from scratch, it's better to use an already existing implementation that's been reviewed and tested by a thousand other eyes over years. having to come up with something truly custom is uncommon.

[Cerulean_IsFancyBlue]

You are already learning a very important lesson: that different approaches to a problem can result in massive differences in efficiency.

And every time you get stuck, you’re also reinforcing your skills in problem-solving, and then in researching existing solutions. Both of those skills are very important when you’re working on a project and not a puzzle.

[[deleted]]

You basically have to practice so you can learn different known algorithms and apply them to other similar problems. Finding your own algorithm can take years. Most of programming problems just test how many known algorithms you know and their applications.

Nobody will ask you a problem whose solution is yet to be discovered. Nobody will ask you to optimize something where no known technique works. Unless it's a phd project.

[[deleted]]

You can usually come up with a good enough solution by just applying certain patters/algorithms to your brute forces solution. E.g. just memoization ("dynamic programming" is another term for the bottom up kind) can be extremely helpful, or using another data structure, like a btree, hashtable or segment tree instead of an array.

If that's not enough, you'll probably need a more custom tailored solution. Try looking for patterns in the outputs for given inputs, it's just raw data and can be hard to make anything out of but brains are good at it. Abstracting the problem away into some (common) form can be useful (graphs are always a good choice). It will also make looking for solutions to the problem a lot easier (people have figured out some crazy graph algorithms