漸近的複雑さ
Chiris OkazakiのPurely Functional Data Structuresを読んでいる。
その中の評価の話のなかで以下のような記述がある。
Each evaluation order has its advantages and disadvantages, but strict evaluation is clearly superior in at least one area: ease of reasoning about asymptotic complexity. In strict languages, exactly which subexpressions will be evaluated, and when, is for the most part syntactically apparent. Thus, reasoning about the running time of a given program is relatively
straightforward. However, in lazy languages, even experts frequently have difficulty predicting when, or even if, a given subexpression will be evaluated. Programmers in such languages are often reduced to pretending the language is actually strict to make even gross estimates of
running time!
strict evaluation は、 ease of reasoning about asymptotic complexity において、lazy evaluationよりも優れているというそうだ。
strict languagesはimperative languageのことで、本書ではC言語などを指していると思われる。
strict evaluation -> https://ja.wikipedia.org/wiki/先行評価
Strict evaluation, also known as eager evaluation, is the evaluation strategy used by most functional programming languages where an expression is evaluated as soon as it is bound to a variable. Strict evaluation is in direct opposition to lazy evaluation, where the evaluation of an expression is delayed until its value is needed. Haskell is the most popular programming language that uses lazy evaluation. Most programming languages use strict evaluation for function arguments (sometimes referred to as parameters) such as Java, Scheme (a Lisp language), and JavaScript.
Asymptotic Complexity
「漸近的複雑さ」というものらしい。
定義らしきもの
The limiting behavior of the execution time of an algorithm when the size of the problem goes to infinity. This is usually denoted in big-O notation.
ふむ。アルゴリズムの実行時間に関するものらしい。特にproblem、アルゴリズムで処理したいデータつまりinputのことであるが、それが無限に近づく時の実行時間を表現するもののようだ。
Asymptotic Analysis
Asymptotic complexityに関して、推定方法（果たして推定なのか）として、Asymptotic Analysisというもの出てくる。
ランダムなサイトで確認してみよう。
Using asymptotic analysis, we can get an idea about the performance of the algorithm based on the input size. We should not calculate the exact running time, but we should find the relation between the running time and the input size. We should follow the running time when the size of input is increased.
For the space complexity, our goal is to get the relation or function that how much space in the main memory is occupied to complete the algorithm.
こちらも、このAnalysisのcontextが明らかで、わかりやすい。
アルゴリズムのperformance analysisの一つのようだ。
Asymptotic Analysis is the big idea that handles above issues in analyzing algorithms. In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don’t measure the actual running time). We calculate, how the time (or space) taken by an algorithm increases with the input size.
こちらのMITの講義の動画でアルゴリズムのperformanceの話が出てくる。17:30以降あたり。
complexityの表現
ランダウの記号やAsymptotic Notationsでさらに知ることができる。
Discussion