将问题分解为若干个规模小但类型原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来求原问题的解.
三个步骤
分解:把问题分解成若干个规模小的子问题,这些子问题是原问题的规模小的实例
解决:递归求解各个子问题,如果规模足够小,直接求解
合并:根据子问题的解,求原问题解
分解:把待排序N个元素的序列分解成两个N/2个元素的子序列
解决:递归地排序两个子序列,但子序列长度为1.递归返回
合并:把两个已排序的子序列,合并成一个已排序的序列
|
|
merge方法合并N/2长两个序列需要N长时间.当子序列长度为1,递归返回时,merge合并N/2对长度为1的子序列,即总时间N.
然而这递归过程可以建立一个二叉树,N个元素当做叶子节点.非叶子节点即是两个子节点序列合并而成. 所以这颗树的高度是logN,每一层合并的时间是N.因此归并排序时间复杂度是:NlogN
有时候需要求解和原问题完全不一样的子问题,称为合并子问题步骤的一部分.
一个序列A[n],按着分治思想把序列分成A[1,mid]和A[mid+1, n]序列.这时,最大子数组要么在A[1,mid]里面,要么在A[mid+1, n]里面,还有可能是跨中间A[i,mid,j]序列中
|
|
若已知A[1…j]的最大子数组，A[1…j+1]的最大子数组要么是A[1…j]的最大子数组，要么是某个子数组Ai…j+1.在已知A[1…j]的最大子数组的情况下，可以在线性时间内找出形如A[i..j+1]的最大子数组
|
|
如果一个数组A[k..j]求和得到负值，那么数组A[k..j+1]的最大子数组肯定不会是A[k..j+1]，因为A[k..j]+A[j+1]1234567891011121314151617181920public static Tuple findMaxOfLine2(int[] A, int l, int r){ int tempSum=0; int sum=Integer.MIN_VALUE; Tuple<Integer, Integer, Integer> tuple = new Tuple<>(); int k=0; for(int i=l;i<=r;i++){ tempSum+=A[i]; if(tempSum > sum) { sum=tempSum; tuple.left = k; tuple.right=i; } if(tempSum < 0) { tempSum=0; k=i+1; } } tuple.sum = sum; return tuple;}
插入排序是使用了增量方法,在已经排序好的子数组A[1..j-1]中插入A[j],产生已经排序好的子数组A[1..j]
|
|
外层循环n-1次,内层循环次数,也是元素的比较次数
最好情况:数组A[n]是已经排序好的,那么元素比较次数是1
最坏情况数组A[n]是反序的,那么元素比较次数是n-1
所以最好情况是n,最坏情况是n^2
He can sing and he can dance.
He can sing and dance.
He can both sing and dance.(both…and…两者都)
He can not only sing but also dance.(不但..而且)
You may go or stay.(或者)
Hurry up or you’ll be late for school.(不然)
Either Tom or Jerry must sing a song.(eithor..or…或者…或者(二选一))
Neither Tom nor Jerry must sing a song.(neithor..nor…两者都不(二全否))
Many is a pretty girl, but i don’t like her.(但是,然而)
Many is a pretty girl, yet he doesn’t like her.(但是,然而(惊讶))
Many is a pretty girl. However, i don’t like her.(但是,然而(没有连接作用,起转折副词))
主语——名、代（主格）
谓语——动词
表语——名、代、形、副(少量)、介宾
宾语——名、代（宾格）
代词主格：做主语
I,You,He,She,It,We,You,They
代词宾格：动后介后
me,you,him,her,it,us,you,them
Tom loves him.
代词形容格:跟着名词
my,your,his,her,its,our,your,their
her friend 她的朋友
代词名词格
mine,yours,his,hers,ours,yours,theirs
The car is yours
名词格=形容格+名词
The book is mine. Yousr is here.这本书是我的，你的在这儿
反身代词：主语和表语指同一个人，宾语用反身代词
myself,yourself,himself,herself,itself,ourselves,yourselves,themselves
名前,名后做定语
it is an apple different from yours
be后做表语
| 动词 | 规则变化 | 不规则变化 |
|---|---|---|
| 比较级 | +er | y,e,双,多 |
| 最高级 | +est | y,e,双,多 |
特殊变化
good -> better -> best
bad -> worse -> worst
many/much -> more -> most
little -> less -> least
far -> further/farther -> furthest/farthest
old -> older,elder -> oldest, eldest
辅音字母+y:变y为i加er, est
easy -> easier -> easiest
元音字母+y:直接加ed
qray -> qrayer -> qrayest
以e结尾:直接加r,st
large -> larger -> largest
双写原则:辅元辅+重读(单音节)
hot -> hotter -> hottest
双写原则:辅元辅+重读(多音节)
beautiful -> more beautiful -> most beautiful
1 原级比较(和…一样)
肯定句 A…as + adj/adv原级 + as + B
you are as tall as Tom
they can learn Englis as fast as you.
否定句 A…not as/so + adj/adv原级 + as + B
you are not as/so tall as Tom
He will be back as soon as possible(他会尽快回来)
He will be back as soon as he can
He is running as fast as possible(他正在尽力奔跑)
I will help you as much as possible.(我会尽可能多的帮你)
2 比较级: A… + 比较级 + than B
china is larger than USA.
than 后面代词的写法
Henry is taller than (I am / I / me(口语))
3.最高级, the + 最高级
she is the most beautiful girl in her class
she is one of the most beautiful girls in the world(最美丽之一)
修饰形容词，直接放前面
例如：very happy
修饰动词，放在反面
例如：Tom misses his sister very much. Tom非常想念他的姐姐 very much 修饰 miss
修饰名词，放在后面
例如：the kids there 哪里的小孩
可以和名词的单数、复数和不可数搭配，表达这个，这些
元音字母a,e,i,o,u
挨着最近的词开头发元音 + an
an old man
an hour
This is water 这些是水
That is water 那些是水
these are books
those are books
变化规则
| 动词 | 规则变化 | 不规则变化 |
|---|---|---|
| 动s/名复 | +s | s,o,f,y |
| 动过/动分 | +ed | y,e,双 |
| 动ing | +ing | y,e,双 |
特殊变化
man->men,woman->women,child->children,tooth->teeth,foot->feet.
s/ss/sh/ch/x结尾的单词+es
bus->buses,dish->dishes,watch->watches.
o原则 1)有生命+es
hero->heroes, potato->potatoes, tomato->tomato
2)无生命 + s
zoo->zoos, photo->photos.
f,fe原则 1)多数变f,fe 为ves
wife->wives, knife->knives, yourself-yourselves.
y原则 1)辅音字母+y, 变y为i加es
baby->babies, city->cities
2)元音字母(a,e,i,o,u)+y, 直接加s
day-> days, boy->boys
特殊变化
put->put--put, cut->cut--cut, say->said--said, pay->paid--paid,
lay->laid--laid, run->ran--run, swim->swam--swum, begin->began--begun
know->knew-known, get->got--got
辅音字母+y:变y为i加-ed
hurry->hurried--hurried, study->studied--studied,try->tried--tried
元音字母+y:直接加ed
play->played--played, stay->stayed--stayed
以e结尾:直接加d
smile->smiled--smiled, dance->danced--danced, agree->agreed--agreed
lie(撒谎)->lied--lied, die->died--died, tie->tied--tied
双写原则:辅元辅+重读:单音节(单多音节看有几个发音元音字母)
stop->stopped--stopped, plan->planned-planned
双写原则:辅元辅+重读:双,多音节
regret->regretted--regretted, listen->listened--listened
以y/w/x结尾的词,不管符合双写原则与否,均不双写
play->played--played
snow->snowed--snowed
fix->fixed--fixed
l结尾也符合辅元辅原则的词,英式双写,美式不双写
travel-> traveled/travelled
cancel-> canceled/cancelled
特殊情况
be -> being, see -> seeing, agree -> agreeing
以y结尾,直接加ing
play->playing, pay->paying
以e结尾,去e加ing
write -> writing, dance -> dancing
以ie结尾,去ie加ying
lie -> lying, die -> dying, tie -> tying
双写原则:辅元辅+重读:单音节(单多音节看有几个发音元音字母)
stop->stopping, plan->planning
put -> putting, get -> getting
双写原则:辅元辅+重读:双,多音节
begin -> beginning, forget -> forgetting
visit -> visiting(重读在前面)
以y/w/x结尾的词,不管符合双写原则与否,均不双写
play-> playing, fix->fixing
l结尾也符合辅元辅原则的词,英式双写,美式不双写
travel-> traveling/travelling
cancel-> canceling/cancelling
不能单独当谓语的动词形式
doing(主动), done(被动), to do(将要)
being, been, to be
Cleaning the room is difficult.
it is difficult to do clean.
you work is cleaing the room.
he will give up smoking
介词后+动ing
give up 放弃
think of 想起
feel like 喜欢
look forward to 盼望
be interested in 感兴趣
(多数)动后+to do
want to do, hope to do, expect to do
agree to do, manage to do, decide to do
(少数)动后+doing
enjoy doing, dislike doing
finish doing, mind doing
(个别)动后+to do / doing 意义一样
begin, start, continue, like, love, hate
(个别)动后+to do / doing 意义不一样
stop to do, forget to do, remember to do, regret to do 去做
stop doing, forget doing, remember doing, regret doing 已做
名前名后做定语
the dancing girl
the girl dancing in the room
名词前要么有a, the, 或者复数不需要加,要么this, that, your, my
做主语
the girl is cute
be后(表语)
i am a girl
介后(宾语)
i look at the girl
动后(宾语)
i like the girl.
句子扮演名词
that + 肯定句
that he speaks English
that + 否定句
that he doesn't speak English
if/whether + 陈述句
Does he speak English?
if/whether he speaks English
特殊疑问句:问主语,当名词,语序不变
who speaks English
特殊疑问句:问非主语,当名词,特问词+陈述句
what dose he speak?
what he speaks
名词性从句意思
whether he has finished his work 他是否已经完成了工作
how you learn English 你学英语方法
where he was born 他出生的地方
what will happen 将要发生的事件
what he said 他说过的话
当主语
每个人必须学英语不是我的主意
That every one must learn English is not my idea
It is not my idea that everyone must learn English(It是形式主语)
当表语
消息是每个人必须将英语
the news is that everyon must speak english
介后+当宾语
他会放弃他拥有的东西
he will give up what he has
动后+当宾语
我不相信他将英语
i don't believe tha he speaks english
修饰名词，对名词进行限定的语言. 追着名词跑(名前,名后)
写在名前
形容词,doing, done
写在名后
个别副词(方位),介词短语,to do, 定语从句
形容词短语,doing短语,done短语
并列形容词短语可以放前面 the big and round apple(又大又圆的苹果)
形容词做定语：形容+名
a clean room
介宾做定语：名+介宾
the box on the table 桌子上的盒子
部分副词做定语：名+副词
children there 哪里的小孩
句子当定语(翻译 找主干,定位置(句子放名词后面),关系词(who/which),顺着写)
我是喜欢你的人
i am the person who/which(人/物) likes you
i am the person who you like
the person (who likes you) is me
人当主语的,可以用who/that. 当宾语的可以用who/that/whom
物,可以用which/that
当宾语时,关系词可以省略
is there anything i can do for you
is there anything that i can do for you
is there anything (that i can do for you)
主系表结构或There Be
谓语: is/am are
主谓(宾)结构
谓语: 动原/动s, 助动词do, does(助动词出现,谓动用原性)
主系表结构或There Be
谓语: was were
主谓(宾)结构
谓语: 动过, 助动词did(助动词出现,谓动用原性)
出现过去的时间,用一般过去时
just now, yesterday, last Saturday, last Sunday, three days age, long long age
语境暗示了动作发生在过去
when did you come back ? 你什么时候回来的?
I loved you. 我爱过你
主系表结构或There Be
谓语: whil be
主谓(宾)结构
谓语: will + 动原
否定句 will not + 动原
疑问句 Will you be in Paris tomorrow ?
Will there be a party next week ?
特殊疑问句 Who will visit us tomorrow ?
What will he do tomorrow ?
谓语: is/am/are going to + be
谓语: is/am/are going to + 动原
疑问句: Are you going to know my story?
特殊疑问句 Who is he going to Be?
表示意愿 用will
Marry me!I will make you happy.
Will you help me?
表示预测 用will/Be going to
It will be warm tomorrow. 明天会变暖和
表示计划,先规划好 用Be going to
I have the pen and the paper.
I am going to draw a picture for you.
缩写
will not = won't
I will = I'll
出现将来时间,用一般将来时
in three days 三天后
tomorrow, the day after tomorrow 后天, next week
soon 要开始,很快
情态动词 + 动原
肯定句:You can help me.
否定句:You can not help me.
疑问句:Can you help me?
特殊疑问句: Who can help me? Who can you help?
####can, could
could 是can 过去式
表达能力, could并表示过去式
We can use WeChat now.
求人办事, could并不表示过去式,表示语气,could更委婉
Can/Could you open the door?
请人允许 could并不表示过去式,表示语气,could更委婉
Can/Could I sit here ?
Can/Could I help you ?
猜测,意思可能
He can be our teacher.
Anything can happen.
might是may的过去式
请人允许
May I help you?
猜测,意思可能
He may be our teacher.
必须
I must learn English.(客观)
I have to learn English. (不得不)
必须不,禁止
I mustn't learn English.
I don't have to learn English.(不必须)
I needn't learn English.(不需要)
猜测,意思肯定是
He must be out teacher.
He must be over forty.
can < will < could < would
Can you do me a favor ? I’d like to, but …
can < could < may < might(礼貌过头)
Can i smoke here? Yes please. Sorry, you can’t
肯定句(100%) > must(95%) > can/could/may/might(50%) > can’t(5%) > 否定句(0%)
He must be a smoker.
主系表结构或There Be
谓语: is/am/are + being
主谓(宾)结构
谓语: is/am/are + 动ing
否定句: She is not doing her homework at home.
疑问句: Is She doing her homework at home?
What are you doing?你干什么呢?
主系表结构或There Be
谓语: was/were + being
主谓(宾)结构
谓语: was/were + 动ing
一般过去时表示过去的时间完整做了某事
I read a book yeaterday (看完了)
过去进行时表示过去的时间正在做某事
I was reading a book just now (未知是否读完)
I went shopping this morning.
主系表结构或There Be
谓语: has/have + been
主谓(宾)结构
谓语: has/have + 过分
Jake has finished her homework.
Jake has not finished her homework.
Has jake finished her homework?
who has finished the homework?
what has Jake finished?
一般过去时:只是陈述一件发生的事件,与现在无关
现在完成时:过去动作对现在有影响
Jake has just(刚刚) turned off the light.(别人不用去关灯)
一般过去时:无法判断是否持续
现在完成时:表示动作现在持续
He has lived her for 4 years (现在还住在这儿)
He lived here for 4 year.(住过,不知道是否继续住)
How long have you learned English ? 你学英语多长了?(现在依然在学)
现在完成时的信号词: 到现在为止
so far, up to now, till now, by now
since + 过去的时间系列
since three days age
since you left
一般过去时的信号词
just now
last yesterday
修饰动词，介宾、副词担当，放在句首、句尾和句中都可以
表示频度副词, 可以放句中. 例如: I often go shopping.
She felt sad just now(just now 时间状语)
She felt sad when you said that(when 当…时)
While I was dancing, Ann was singing(while 当…时)
As she sang, tears ran down her cheeks.(as 当…时)
Please let me know before you come.(before 在…之前)
Please read the letter after i have left(after 在…之后)
I have not met him since he left(since 自从)
Mr.Green waited until Tom came back.(until 直到…)
She began to sleep as soon as the class was over.(as soon as 一…就)
You should stay where you are(where …的地方)
你应该待着你所待的地方
People like to live where it’s near rivers.
I missed the bus, because i got up late. (because 因为)
Since everyone is here, let’s get started.(since 既然)
As he was not ready, we went without him.(as 由于)
He likes the girl, for he often helps her.(for 因为 不是原因状语从句)
I got up late, so I missed the bus. (so 因此,所以)
He will comee if he is invited. (if 如果)
He won’t come unless he is invited.(unless 除非)
Call me in case you are in trouble.(in case 万一)
You can stay here as long as you keep quiet.(as long as 只要)
So far as I know, he is a good boy.(so far as 据..所)
结果状语从句
He is so kind that everyon likes him.(so..that so+adj/adv 如此..以至于…)
He is such a kind boy that everyone likes him.(such…that… such+n 如此…以至于…)
He was too young to understand the book(too…to…太…不能… 不是结果状语从句)
We study hard in order that we can pass the test.(in order that …为的是)
We study hard so that we can pass the test.(so that 为的是)
Although/Though he is young, he has read lots of books.(尽管)
Even if/Even thouth it rains tomorrow, we’ll not change our plan(即使)
No matter who/Whoever he is, he must arrive on time(无论)
主语+be+表语
肯定句:He is in the car.
否定句:He is not in the car.
一般疑问句:Is he in the car? Yes,he is. No,he isn’t.
谁在车里？
特殊疑问句——提问主语:Who is in the car?
疑问词+is,am,are+主语？
他在哪儿？
特殊疑问句——提问非主语:Where is he?
I am -> I’m
He is -> He’s
It is -> It’s
They are -> They’re
I am not -> I’m not
is not -> isn’t
are not -> aren’t
主语+非be+(宾语)+状语
否定句：非三单+do not+动原+
一般疑问句:Do+非三单+动原+
特殊疑问句——提问主语：语序不变
特殊疑问句——提问非主语：特助主谓，特殊疑问词+主动词do+非三单+动原+
否定句:三单+does not+动原+
一般疑问句:Does+三单+动原+
特殊疑问句——提问主语：语序不变
特殊疑问句——提问非主语：特助主谓，特殊疑问词+主动词does+三单+动原+
人称代词：第三人称 -> he、she、it
指示代词：this、this book、that、that dog
名词:单数，不可数名词
人称代词:I you we they
指示代词:these、those
名词:复数
肯定句:They learn English every day.
他们每天不学英语。
否定句:They don’t learn English every day.
他们每天学英语吗？
一般疑问句:Do they learn English every day?
谁每天学英语？
特殊疑问句——提问主语:Who learn English every day?
他们每天学什么？
特殊疑问句——提问非主语:What do they learn every day?
(There + is/are)(存在) + 名词 + (地点)
There 不是主语，只是占主语位置。所以is/are由后面名词决定。
表达存在，而have表示拥有，例如：我有三辆车 I have three cars.
There is a cat and two dogs under the tree.
There are two dogs and a cat under the tree.
肯定句:There are many students in the classroom
否定句:There are not many students in the classroom(some 在否定句中变成 any)
一般疑问句:Are there many students in the classroom?
教室里有多少同学？
特殊疑问句:How many students are there in the classroom?
How much + 不可数名词+is there + 地点
How many + 可数名词 + are there + 地点
主谓（宾）
主系表
there be
方式、地点、时间
从小到大
句首状语
每天6点他在家写作业吗？
Dose he do his homework at home at six every day ?
