This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

preface

In this article, we will explain the knowledge needed to write a Fibonacci sequence with time complexity of log(n).

Try again

Linear algebra

Where does linear algebra come from?

So this is definitely going to be linear systems, but what are linear systems?

{ a1x1 + a2x2 + a3x3 = b1,

a4x4 + a5x5 + a6x6 = b2,

. }

It’s a system like this, where the linear equation is one row.

Equations to write longer and longer, to write more and more, so I took the system of linear equations abbreviated into matrix.

|

a1 a2 a3

a4 a5 a6

|

Here write out the effect is not very good, students can search baidu.

The advent of matrices helped us to calculate more complex algorithms, and brought generations of college students down under linear algebra.

I have almost all of the linear algebra I learned in college, so I’m not going to mess it up, and the link is at the end of the article, if you’re interested, but all we need to know is that we’re going to use matrices.

This paper needs to use the matrix multiplication operation, which is as follows:

|

|a1 , a2|,

|a3 , a4|

| × |

|b1 , b2|,

|b3 , b4|

| = |

|a1 b1 + a2 b3 , a1 b2 + a2 b4|,

|a3 b1 + a4 b3 , a3 b2 + a4 b4||

Second order constant coefficient homogeneous linear recursive sequence

The Fibonacci sequence is a quadratic linear recursive sequence with constant coefficients.

What is a homogeneous linear recursive sequence of second order constant coefficients?

The second order constant coefficient homogeneous linear recursive sequence is such that an = C1a (n-1) + c2a(n-2), where c1,c2 are constants and the numbers in () are subscripts.

Well, if it is A second order constant coefficient homogeneous linear recursion sequence, it will have A second order matrix, can satisfy the rules of the series: | F (n) F (n – 1) | | = F (n – 1) F (n – 2) | * A. A is A matrix.

It doesn’t matter if you don’t know, we can use the analogy of X to the N, we can reduce time by moving bits around, rather than multiplying over and over again.

The secret to reducing time complexity to log n

Let’s write an X to the N.

Let’s start with a regular for loop:

private long calculationPower(long base, long power) { long result = 1; for (; power ! = 0; power--) { result *= base; } return result; }Copy the code

If it’s 2 to the 100, it’s going to run 100 times in n time.

When we optimize it by moving bits:

private long calculationPower1(long base, long power) { long result = 1; long temp = base; for (; power ! = 0; power = power >> 1) { if ((power & 1) ! = 0) { result *= temp; } temp *= temp; } return result; }Copy the code

The code works and the results are accurate.

The binary of 100 is 1100100, which means that instead of going through 100 times, you only need to go through 7 times!

14 times more efficient!

I didn’t know anything about it when I first learned it.

  1. Why does Temp multiply itself in every loop?
  2. Why in(power & 1) ! = 0Only whenresult *= temp;.

First, because every time power moves to the right, we’re actually dividing power by 2, temp stores the result of the current bit being X to the n. So the most intuitive example is if you look at the binary code, 6 =110, and these three binary numbers represent 4, 2, 1, and you plug them into 2 ^ 6, and when you get to the first 1 in binary 110, 2 =10, result = 4, so you multiply it twice, and the remaining 1 represents the 2 ^ 4, In the previous loop, temp multiplied by itself (4 times 4) to the 2 ^ 4, so temp multiplied by itself.

The second point, like converting binary to decimal, is that the current bit must be 1 in order to be considered valid.

(FOR the first point, I was haggard, and it took me a long time to express it. Personally, AS long as the examples can be understood, I may have some problems in my personal expression.)

The last

Now that we’ve seen how to reduce the time complexity from O (n) to O (log (n)), there’s one more thing we need to do to write down the time complexity of O (log (n)).

To be continued…

Here is a programmer Xu Xiaobai, daily algorithm [is] my new open a column, primary record my daily learning algorithm, here also hope that I can stick to the daily learning algorithm, don’t know whether this article style you like, don’t mean you free praise, your thumb up, collection, and comments are after work I insist on more power.