It's a huge meme among the high school students attending LUISS lessons about competitive programming, each year the "know it all" ends up saying "I can get fib(N) in almost O(1)"
Can't get over the fact that the "God-Tier" Programmer is concerned about time & space complexity and speed and then chooses to use Python of all languages lol
For the Fibonacci sequence, if you just need a specific number of it, you can use matrix exponentiation and calculated really large indices very quickly
@@kjl3080 idk what that is. I solved it by manually deriving an f(2n) and f(2n-1) function in terms of f(n) and f(n-1) then just cached the immediate previous states. This resulted in O(log(n)) time and O(1) space. code: " def fib(self, n: int) -> int: f0 , f1, r0, r1, i = 1, 1, 0, 1, 1 while i
That’s noob ?!?! My lord I have an odyssey of a journey ahead of me 😂😂 but I’m all for it , fell in love with coding after looking at videos and stuff and had the urge for years , I quite hate my job so I said fuck it , I wanna learn and make a career out of this because even if it’s hard I find it incredibly fascinating
@@padraighill4558 x^2-x-1 *nerd* tho u dont even need generating functions or characteristics polynomials, because Q(sqrt(5)) is kinda intuitive due to similarity with complex numbers. Or just use matrices, it works just the same. But its better to use polynomials division for longer linear recurrences, cuz O(k^2logn) is better than O(k^3logn). I just like the idea of using Q(sqrt(5)), it can mathematically prove some very fun properties
4 месяца назад
you are absolute god expect you are appending all the useless values to list, instead of using using 2 variables
Why can't you solve this in O(1)? It's possible, you "just" find the closest integer (round half up) where F(n) = phi^n / sqrt(5) where phi is the golden ratio [1+sqrt(5)]/2. You can grab the 1 billionth Fibonacci number if your language's number representation can handle arbitrarily large numbers.
This isn’t God Tier.. it might be better than the recursive because it’s not exponential but linear. But the space complexity is linear and could be constant: num1 = 0 num2 = 1 for loop.. temp = num2 num2 += num1 num1 = temp return num2 Something like that
I would just write absolutely garbage and slow code but write it in a language like c++ or rust so it's fast. This may mean i am a noob programmer but i digress
While I agree that storing the entire array is not needed for a single call to this function, if we make the array static (reusable between function calls), we effectively get a cache. At any point, if we have solved the problem up to size M and n M, we just append to our cache until we solve for n, making n the new largest solved problem. Assuming that the inputs follow some reasonable probability distribution without too heavy of a tail and are uncorrelated, then the runtime should converge to an average of O(1).
It's funny that my uni professor solved the fib question with recursion and I solved it with iteration on the test and I got a 0 for it. I talked with him, googled in the front of him to prove that it can be solved with a loop to get my marks on test.
Any recursive problem can be solved with a loop, this is programming 101 and does not need proving. Some problems are just more suited for recursive solutions. Maybe the requirement was to use a recursive approach?
Nice, meme. But for anyone serious about this. Part 1 was the god-tier programmer. Part 2 was the noob one.. It's called premature optimization, which is pointing and wrangling with stuff that just works fine. Programmers go from bad, to worse, to good. The good ones know to appreciate working code and some level of readability. Anything else usually just burns money.
Having that said! Being able to go from recursive to iterative is very useful. It doesn't take too much to buffer overflow. Just don't default to it. Default to simple and readable. It's an optimization. Always start with simple and readable. Always, always.. it works, it works... If you for some reason cannot understand that.. We must be on different planets.
@@g3mint446 This is not premature optimization, the quote is always misinterpreted when it's actually intended to talk about micro-optimizations. Here, the algorithm is changed to a more efficient one. Also, since we're talking about readability, I'd say the second algorithm is much more readable considering it's much closer to what an human would actually do to manually calculate the Fibonacci sequence instead of the recursive solution. Finally, saying the first solution "just works fine" is wrong in my opinion considering it runs in non-polynomial times when there exists many simple polynomial time solutions and the non-polynomial time solution is unable to be used in a real world context considering it gets so slow it can't calculate numbers past like 60-70 in a reasonable amount of time.
@@anto_fire8534 I have to agree with you there. But only if your team think it's the most readable and simple way to write code. If you don't have a clear need to rewrite readable code, why would you? I can do a million things to improve something, it doesn't mean I should. You get the most value from code that is readable, maintainable and working (not some smart ass genious, waste of time code). Some times you don't even need to read it again, it should just work. It is all about time management, and there are cases where scrapping the thing and making it just work is preferable to anything else. Anyone who call themselves an expert but cannot realize this, is not an expert (those people are lying to themselves). I have worked with horrible code and great code. I very much value simple code, but some times the code doesn't matter enough to be a priority, the project is, not the code. The project and the solution spec is the priority. That is what the Manager and the Customer has agreed on, and that is what they need you to help them with. Not a single thing beyond. If you have suggestions to do more, it should be clearly reported and discussed. That is my obligation as a developer. That is my job. Itching my brain and having arrogant opinions is not. I get work done fast and as ordered, that is my job. That is how I keep customers and managers happy. Not by being a genious. Your job is not your company, you don't decide how to run it.
Most God-tier is to use closed form - for extra points: I literally used the closed form in real life application - also the inverse of fibonacci (that is: getting back i from the value :-) )
This is decent for most real world applications but an O(n) algorithm is too lame to be called god tier imo. Use matrix exponentiation and we have O(logn).
Wait why I feel like I'm learning wrong way I did exactly what is best and then I was taught to do recursion 😮 that's not right it's like the simpler the better
I got that question and couldn't solve it because he didn't let us use chatgpt which is very helpful I was learning from it and in Google there is diffrent approach for it with math but that good too
Bruh i remember doing this question, its was one of my first. Took me like 3 hours because i was using c++ and i had only previous knowledge in JS. I solved it, tried to teach it to a friend after a week, brain fog, couldnt solve it. This was 8 months ago, i can solve medium and hard problems on leetcode, currently at 130 solved. I could solve most easy questions in under 5min. Crazy to think about.
Fibonacci is the goto example for recursion. Sure it can be solved iteratively or linearly(Binet's formula), but at some point every god programmer solved it recursively. 😅
Fibonacci is the goto example for recursion. Sure it can be solved iteratively or linearly(Binet's formula), but at some point every god programmer solved it recursively. 😅
Fibonacci is tail recursive. You will gain nothing in forcing the liniar loop, it gets transformed to that internally by the CPU anyway. If you really want to go all in, you have an ugly but working mathematical solution. The problem reduces to gaining a precise implementation of SQRT.
@GregHogg Actually if you write tail recursive functions you will get the same time and space complexity :) Stack recursive functions are bad of course
The God tier would use Matrix based calculation for logarithmic space and time for the most optimal solution... My disappointment is immeasurable and my day is ruined.
@@Ibra_ There is. You learn it in Linear Algebra courses in colleges. Actually any linear recursive defined function like fibonacci has general solution.
Why are you appending to the list, wasted time resizing the list. why not initialise the entire array first, ans = [1] * n Or even better, use a deque from collections
