How to calculate complexity algorithm code program?

Question

Bakka 2014-1-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/113940-how-to-calculate-complexity-algorithm-code-program

评论： Walter Roberson 2020-4-20

Hi everyone, I've build program, now I want to calculate complexity algorithm ? could you please let me know how to do that? is there any reference for calculation process? Many thanks

3 个评论
显示 1更早的评论隐藏 1更早的评论

Bakka 2014-1-29

Dear Mr. @Yao Li , I build steganography program with cryptography as an security . the method of steganography is pixel value differencing, and the cryptography is use rsa. how can I calculate the complexity algorithm? need your advice, many thanks

Walter Roberson 2014-1-29

We cannot be of assistance in any analysis of RSA; the topic is forbidden for discussion here due to USA laws.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2014-1-28

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/113940-how-to-calculate-complexity-algorithm-code-program#answer_122447

You can google the topic.

It has been proven that there is no possible deterministic algorithm which can calculate the Algorithmic Complexity of all possible programs.

MATLAB does not provide any routines to calculate Algorithmic Complexity.

2 个评论
显示无隐藏无

Hazim Nasir 2020-4-19

Kindly, Can you cite a reference that:

that there is no possible deterministic algorithm which can calculate the Algorithmic Complexity of all possible programs.

Walter Roberson 2020-4-20

This is a simple consequence of the (Turing's) Halting Theorem.

It is not possible to write a program, P1, that can take the code for any arbitrary program, P2, as input, with P1 telling you whether P2 halts on all possible inputs. The proof involves deliberate infinite loops and proof by contradiction on feeding a slightly modified version of P1 to itself. There are tight connections to Goedel's Incompleteness Theorem, that there are statements that are true but which cannot be formally proven to be true.

Anyhow, if you cannot write a program that can predict with certainty whether any given program will halt or not, then you cannot predict the algorithmic complexity of all arbitrary programs

请先登录，再进行评论。