IT討論區(56) I巴條數何時了

黎緊呢年mobile app developer 搵唔搵到食

O(1) precompute 後查表外仲有咩方法？

Between, spoiler alert

https://m.hkgolden.com/view.aspx?message=6701927&page=1

你咁算唔算自問自答？

Recursion time係O(2^n), space O(n)
O(n)用dp/loop
O(log n)用matrix multiplication?
O(1)用formula
不過如果係我interview會用O(n) loop計，最快寫到

O(log n) -> Memoization

O(1) 唔答

Memoization即是dp，應該每個數都要計過一次，所以O(n)
O(log n)係要用matrix multiplication or formula derived from it

O(1)有條直接揾到nth fib嘅formula

又要比人壓價

No, my old post in hkgolden does not cover O(1) Fibonacci. I don’t think you can do O(1) without precomputation.

Not really. you can do O(log n) time and O(1) space using matrix multiplication with memorizing anything.

What is the time complexity for evaluating the close for of Fibonacci numbers? How long does it take to compute a^n for an arbitrary n?

I meant without memorizing, sorry

屌😂

U can if you consider math is a O(1) oracle, which is not a really bad consideration as pow is slow anyway

Math.pow我記得係O(1)

You cannot consider maths to be O(1). Otherwise there is no point in studying multiplication algorithms for example. You can only treat basic arithmetic operations for small numbers to be O(1) like 64 bit. Multiplying two really big numbers is not O(1) for example.

咁O(1)就無solution了，最快是O(log n)

Ok 我應該講清楚 個function declaration係int f(int n)
因為我個時係比人問呢個形式 而唔係比人問bigint

Even if you restrict the range to be 64 bit, pow() may not be O(1). If you compute pow() using a Taylor series approximation with fixed number of terms, you will run into an issue with floating point rounding error. If you use matrix multiplication with integers, the best you can do is THETA(log n) multiplications.

If you restrict your Fibonacci numbers in the range representable by 64-bit integers, you cannot even compute the 100th Fibonacci number without overflow. You might just precompute and use a look up table.

Overflow個point






















因為下一題就係問你咁寫有咩問題