はむこの勉強記録

http://bit.ly/2ktf20t の写し

英作文:木のアルゴリズム

概要

英語でアルゴリズムの解説を書けるようになりましょう。

勉強題材

インド人が書いたHL分解の記事。微妙に冠詞が怪しい感じがあるが、非常に読みやすく英語っぽい表現が勉強できそうな感じがする。

思ったんだけど僕が知らないアルゴリズムを勉強したほうが一石二鳥だったなあ。

Heavy Light Decomposition – Anudeep's blog

勉強したこと

論文英語 - PukiWiki

抜粋

プログラマポインタみたいなやつはyouであわらす。また、遷移はmove。moveがいっぱい連なったものはtravelかreach。what you traveled is a chain which starts from the root node.

a tree with N nodes.

頂点の子と言う時、children of a nodeとはあまり言わなくて、Child nodes of a nodeのほうが自然。

根は、the root nodeとかthe rootとか。

クエリは、do, operateするもの。また、受動態ではa query is answered with O(log n) comp.みたいな感じでanswerと相性が良い

3 chains each size of N/3のような文法無視っぽく見える表現ができる。halfとかもそうなんだけど、sizeが前置詞っぽくなることがある。

decompose A into Bs, such that B is …のように、分解後のものを説明する表現便利。

葉ではないノード non-leaf nodeのようにできる。まじか。

edgeはconnectするconnector。connect A and Bだったり、connector between A and Bだったりする。

考えられる中での最大、みたいな奴は、possible forを使う。

固定のためにeachを使う。for each non-leaf node, the edge connecting the node and its special child is considered as “Special Edge."。というか、non-leaf nodeおもしろくないですか。

どうやら、〜と呼ぶ、みたいなやつをis considered asで表す方法があるらしい。

eachの否定っぽいやつはanyで表現する。

〜計算量で、はwith O(log n) complexity, もしくはin O(log n) time

最悪計算量はMoving is up to O(n) complexityなど。あとmovingみたいなやつとcomplexityが同格なのウケる