ravencrown / fe-learning Goto Github PK
View Code? Open in Web Editor NEW前端知识补全,回顾
前端知识补全,回顾
最好写出四五种布局方式
<style>
body {
margin: 0;
padding: 0;
}
.block1 {
float: left;
background: blue;
width: 300px;
height: 200px;
}
.block3 {
width: 300px;
height: 200px;
float: right;
background: red;
}
.block2 {
margin-left: 300px;
margin-right: 300px;
height: 200px;
background: yellow;
}
</style>
<div class="container">
<div class="block block1"></div>
<div class="block block3"></div>
<div class="block block2"></div>
</div>
<style>
body {
margin: 0;
padding: 0;
}
.block {
height: 200px;
}
.left {
float: left;
width: 300px;
background: red;
}
.right {
float: right;
background: blue;
width: 300px;
}
.main {
background: yellow;
overflow: hidden;
}
</style>
<div class="container">
<div class="block left"></div>
<div class="block right"></div>
<div class="block main"></div>
</div>
<style>
body {
margin: 0;
padding: 0;
}
.block {
height: 200px;
}
.container {
position: relative;
}
.left {
position: absolute;
top: 0;
left: 0;
width: 300px;
background: red;
}
.right {
position: absolute;
top: 0;
right: 0;
width: 300px;
background: blue;
}
.main {
background: yellow;
}
</style>
<div class="container">
<div class="block left"></div>
<div class="block main"></div>
<div class="block right"></div>
</div>
<style>
body {
margin: 0;
padding: 0;
}
.container {
display: flex;
}
.block {
height: 300px;
}
.block1,
.block3 {
/* width: 300px; */
flex: 0 0 300px;
}
.block1 {
background: blue;
}
.block2 {
background: yellow;
/* flex: 1 0 0; */
flex: 1;
}
.block3 {
background: red;
}
</style>
<div class="container">
<div class="block block1"></div>
<div class="block block2"></div>
<div class="block block3"></div>
</div>
<style>
body {
margin: 0;
padding: 0;
}
.container {
display: table;
width: 100%;
}
.block {
height: 200px;
}
.left,.right,.main {
display: table-cell;
}
.left,.right {
width: 300px;
}
.left {
background: red;
}
.right {
background: blue;
}
.main {
background: yellow;
}
</style>
<div class="container">
<div class="block left"></div>
<div class="block main"></div>
<div class="block right"></div>
</div>
<style>
body {
margin: 0;
padding: 0;
}
.container {
display: grid;
width: 100%;
grid-template-rows: 100px;
grid-template-columns: 300px auto 300px;
}
.left {
background: red;
}
.right {
background: blue;
}
.main {
background: yellow;
}
</style>
<div class="container">
<div class="block left"></div>
<div class="block main"></div>
<div class="block right"></div>
</div>
<style>
body {
padding: 0;
margin: 0;
}
.block {
height: 200px;
}
.left {
position: relative;
left: -200px;
margin-right: -100%;
width: 200px;
float: left;
background: red;
}
.right {
position: relative;
right: -200px;
margin-left: -200px;
width: 200px;
float: right;
background: blue;
}
.main {
width: 100%;
float: left;
background: yellow;
}
.container {
margin-left: 200px;
margin-right: 200px;
}
</style>
<div class="container">
<div class="block left"></div>
<div class="block right"></div>
<div class="block main"></div>
</div>
JS 异步相关
##ES6 模块化如何使用,开发环境如何打包
本文主要介绍
// util1.js
export default {
a: 100
};
// util2.js
export function fn1(){ console.log("fn1")}
export function fn2(){ console.log("fn2")}
// index.js
import util1 from './util1.js';
import { fn1, fn2 } from './util2.js'
console.log(util1)
fn1()
fn2()
前后端数据交互经常会碰到请求跨域,什么是跨域,以及有哪几种跨域方式,这是本文要探讨的内容。
同源策略是一种约定,它是浏览器最核心也最基本的安全功能,如果缺少了同源策略,浏览器很容易受到XSS、CSFR等攻击。所谓同源是指"协议+域名+端口"三者相同,即便两个不同的域名指向同一个ip地址,也非同源。
同源策略限制内容有:
但是有三个标签是允许跨域加载资源:
<img src=XXX>
<link href=XXX>
<script src=XXX>
当协议、子域名、主域名、端口号中任意一个不相同时,都算作不同域。不同域之间相互请求资源,就算作“跨域”。常见跨域场景如下图所示:
特别说明两点:
第一:如果是协议和端口造成的跨域问题“前台”是无能为力的。
第二:在跨域问题上,仅仅是通过“URL的首部”来识别而不会根据域名对应的IP地址是否相同来判断。“URL的首部”可以理解为“协议, 域名和端口必须匹配”。
这里你或许有个疑问:请求跨域了,那么请求到底发出去没有?
跨域并不是请求发不出去,请求能发出去,服务端能收到请求并正常返回结果,只是结果被浏览器拦截了。你可能会疑问明明通过表单的方式可以发起跨域请求,为什么 Ajax 就不会?因为归根结底,跨域是为了阻止用户读取到另一个域名下的内容,Ajax 可以获取响应,浏览器认为这不安全,所以拦截了响应。但是表单并不会获取新的内容,所以可以发起跨域请求。同时也说明了跨域并不能完全阻止 CSRF,因为请求毕竟是发出去了。
1) JSONP原理
利用 <script> 标签没有跨域限制的漏洞,网页可以得到从其他来源动态产生的 JSON 数据。JSONP请求一定需要对方的服务器做支持才可以。
2) JSONP和AJAX对比
JSONP和AJAX相同,都是客户端向服务器端发送请求,从服务器端获取数据的方式。但AJAX属于同源策略,JSONP属于非同源策略(跨域请求)
3) JSONP优缺点
JSONP优点是简单兼容性好,可用于解决主流浏览器的跨域数据访问的问题。缺点是仅支持get方法具有局限性,不安全可能会遭受XSS攻击。
4) JSONP的实现流程
在开发中可能会遇到多个 JSONP 请求的回调函数名是相同的,这时候就需要自己封装一个 JSONP函数。
// index.html
function jsonp({ url, params, callback }) {
return new Promise((resolve, reject) => {
let script = document.createElement('script')
window[callback] = function(data) {
resolve(data)
document.body.removeChild(script)
}
params = { ...params, callback } // wd=b&callback=show
let arrs = []
for (let key in params) {
arrs.push(`${key}=${params[key]}`)
}
script.src = `${url}?${arrs.join('&')}`
document.body.appendChild(script)
})
}
jsonp({
url: 'http://localhost:3000/say',
params: { wd: 'Iloveyou' },
callback: 'show'
}).then(data => {
console.log(data)
})
上面这段代码相当于向http://localhost:3000/say?wd=Iloveyou&callback=show
这个地址请求数据,然后后台返回show('我不爱你'),最后会运行show()这个函数,打印出'我不爱你'
// server.js
let express = require('express')
let app = express()
app.get('/say', function(req, res) {
let { wd, callback } = req.query
console.log(wd) // Iloveyou
console.log(callback) // show
res.end(`${callback}('我不爱你')`)
})
app.listen(3000)
** 5) jQuery的jsonp形式**
JSONP都是GET和异步请求的,不存在其他的请求方式和同步请求,且jQuery默认就会给JSONP的请求清除缓存。
$.ajax({
url:"http://crossdomain.com/jsonServerResponse",
dataType:"jsonp",
type:"get",//可以省略
jsonpCallback:"show",//->自定义传递给服务器的函数名,而不是使用jQuery自动生成的,可省略
jsonp:"callback",//->把传递函数名的那个形参callback,可省略
success:function (data){
console.log(data);}
});
CORS 需要浏览器和后端同时支持。IE 8 和 9 需要通过 XDomainRequest 来实现。
浏览器会自动进行 CORS 通信,实现 CORS 通信的关键是后端。只要后端实现了 CORS,就实现了跨域。
服务端设置 Access-Control-Allow-Origin 就可以开启 CORS。 该属性表示哪些域名可以访问资源,如果设置通配符则表示所有网站都可以访问资源。
虽然设置 CORS 和前端没什么关系,但是通过这种方式解决跨域问题的话,会在发送请求时出现两种情况,分别为简单请求和复杂请求。
1) 简单请求
只要同时满足以下两大条件,就属于简单请求
条件1:使用下列方法之一:
条件2:Content-Type 的值仅限于下列三者之一:
请求中的任意 XMLHttpRequestUpload
对象均没有注册任何事件监听器; XMLHttpRequestUpload
对象可以使用 XMLHttpRequest.upload
属性访问。
** 2) 复杂请求**
不符合以上条件的请求就肯定是复杂请求了。
复杂请求的CORS请求,会在正式通信之前,增加一次HTTP查询请求,称为"预检"请求,该请求是 option 方法的,通过该请求来知道服务端是否允许跨域请求。
我们用PUT向后台请求时,属于复杂请求,后台需做如下配置:
// 允许哪个方法访问我
res.setHeader('Access-Control-Allow-Methods', 'PUT')
// 预检的存活时间
res.setHeader('Access-Control-Max-Age', 6)
// OPTIONS请求不做任何处理
if (req.method === 'OPTIONS') {
res.end()
}
// 定义后台返回的内容
app.put('/getData', function(req, res) {
console.log(req.headers)
res.end('我不爱你')
})
接下来我们看下一个完整复杂请求的例子,并且介绍下CORS请求相关的字段
// index.html
let xhr = new XMLHttpRequest()
document.cookie = 'name=xiamen' // cookie不能跨域
xhr.withCredentials = true // 前端设置是否带cookie
xhr.open('PUT', 'http://localhost:4000/getData', true)
xhr.setRequestHeader('name', 'xiamen')
xhr.onreadystatechange = function() {
if (xhr.readyState === 4) {
if ((xhr.status >= 200 && xhr.status < 300) || xhr.status === 304) {
console.log(xhr.response)
//得到响应头,后台需设置Access-Control-Expose-Headers
console.log(xhr.getResponseHeader('name'))
}
}
}
xhr.send()
//server1.js
let express = require('express');
let app = express();
app.use(express.static(__dirname));
app.listen(3000);
//server2.js
let express = require('express')
let app = express()
let whitList = ['http://localhost:3000'] //设置白名单
app.use(function(req, res, next) {
let origin = req.headers.origin
if (whitList.includes(origin)) {
// 设置哪个源可以访问我
res.setHeader('Access-Control-Allow-Origin', origin)
// 允许携带哪个头访问我
res.setHeader('Access-Control-Allow-Headers', 'name')
// 允许哪个方法访问我
res.setHeader('Access-Control-Allow-Methods', 'PUT')
// 允许携带cookie
res.setHeader('Access-Control-Allow-Credentials', true)
// 预检的存活时间
res.setHeader('Access-Control-Max-Age', 6)
// 允许返回的头
res.setHeader('Access-Control-Expose-Headers', 'name')
if (req.method === 'OPTIONS') {
res.end() // OPTIONS请求不做任何处理
}
}
next()
})
app.put('/getData', function(req, res) {
console.log(req.headers)
res.setHeader('name', 'jw') //返回一个响应头,后台需设置
res.end('我不爱你')
})
app.get('/getData', function(req, res) {
console.log(req.headers)
res.end('我不爱你')
})
app.use(express.static(__dirname))
app.listen(4000)
上述代码由http://localhost:3000/index.html向http://localhost:4000/
跨域请求,正如我们上面所说的,后端是实现 CORS 通信的关键。
postMessage是HTML5 XMLHttpRequest Level 2中的API,且是为数不多可以跨域操作的window属性之一,它可用于解决以下方面的问题:
postMessage()方法允许来自不同源的脚本采用异步方式进行有限的通信,可以实现跨文本档、多窗口、跨域消息传递。
otherWindow.postMessage(message, targetOrigin, [transfer]);
接下来我们看个例子: http://localhost:3000/a.html
页面向http://localhost:4000/b.html
传递“我爱你”,然后后者传回"我不爱你"。
// a.html
<iframe src="http://localhost:4000/b.html" frameborder="0" id="frame" onload="load()"></iframe> //等它加载完触发一个事件
//内嵌在http://localhost:3000/a.html
<script>
function load() {
let frame = document.getElementById('frame')
frame.contentWindow.postMessage('我爱你', 'http://localhost:4000') //发送数据
window.onmessage = function(e) { //接受返回数据
console.log(e.data) //我不爱你
}
}
</script>
// b.html
window.onmessage = function(e) {
console.log(e.data) //我爱你
e.source.postMessage('我不爱你', e.origin)
}
Websocket是HTML5的一个持久化的协议,它实现了浏览器与服务器的全双工通信,同时也是跨域的一种解决方案。WebSocket和HTTP都是应用层协议,都基于 TCP 协议。但是 WebSocket 是一种双向通信协议,在建立连接之后,WebSocket 的 server 与 client 都能主动向对方发送或接收数据。同时,WebSocket 在建立连接时需要借助 HTTP 协议,连接建立好了之后 client 与 server 之间的双向通信就与 HTTP 无关了。
原生WebSocket API使用起来不太方便,我们使用Socket.io,它很好地封装了webSocket接口,提供了更简单、灵活的接口,也对不支持webSocket的浏览器提供了向下兼容。
我们先来看个例子:本地文件socket.html向localhost:3000
发生数据和接受数据
// socket.html
<script>
let socket = new WebSocket('ws://localhost:3000');
socket.onopen = function () {
socket.send('我爱你');//向服务器发送数据
}
socket.onmessage = function (e) {
console.log(e.data);//接收服务器返回的数据
}
</script>
// server.js
let express = require('express');
let app = express();
let WebSocket = require('ws');//记得安装ws
let wss = new WebSocket.Server({port:3000});
wss.on('connection',function(ws) {
ws.on('message', function (data) {
console.log(data);
ws.send('我不爱你')
});
})
实现原理:同源策略是浏览器需要遵循的标准,而如果是服务器向服务器请求就无需遵循同源策略。
代理服务器,需要做以下几个步骤:
我们先来看个例子:本地文件index.html文件,通过代理服务器http://localhost:3000
向目标服务器http://localhost:4000
请求数据。
// index.html(http://127.0.0.1:5500)
<script src="https://cdn.bootcss.com/jquery/3.3.1/jquery.min.js"></script>
<script>
$.ajax({
url: 'http://localhost:3000',
type: 'post',
data: { name: 'xiamen', password: '123456' },
contentType: 'application/json;charset=utf-8',
success: function(result) {
console.log(result) // {"title":"fontend","password":"123456"}
},
error: function(msg) {
console.log(msg)
}
})
</script>
// server1.js 代理服务器(http://localhost:3000)
const http = require('http')
// 第一步:接受客户端请求
const server = http.createServer((request, response) => {
// 代理服务器,直接和浏览器直接交互,需要设置CORS 的首部字段
response.writeHead(200, {
'Access-Control-Allow-Origin': '*',
'Access-Control-Allow-Methods': '*',
'Access-Control-Allow-Headers': 'Content-Type'
})
// 第二步:将请求转发给服务器
const proxyRequest = http
.request(
{
host: '127.0.0.1',
port: 4000,
url: '/',
method: request.method,
headers: request.headers
},
serverResponse => {
// 第三步:收到服务器的响应
var body = ''
serverResponse.on('data', chunk => {
body += chunk
})
serverResponse.on('end', () => {
console.log('The data is ' + body)
// 第四步:将响应结果转发给浏览器
response.end(body)
})
}
)
.end()
})
server.listen(3000, () => {
console.log('The proxyServer is running at http://localhost:3000')
})
// server2.js(http://localhost:4000)
const http = require('http')
const data = { title: 'fontend', password: '123456' }
const server = http.createServer((request, response) => {
if (request.url === '/') {
response.end(JSON.stringify(data))
}
})
server.listen(4000, () => {
console.log('The server is running at http://localhost:4000')
})
上述代码经过两次跨域,值得注意的是浏览器向代理服务器发送请求,也遵循同源策略,最后在index.html文件打印出{"title":"fontend","password":"123456"}
实现原理类似于Node中间件代理,需要你搭建一个中转nginx服务器,用于转发请求。
使用nginx反向代理实现跨域,是最简单的跨域方式。只需要修改nginx的配置即可解决跨域问题,支持所有浏览器,支持session,不需要修改任何代码,并且不会影响服务器性能。
实现思路:通过nginx配置一个代理服务器(域名与domain1相同,端口不同)做跳板机,反向代理访问domain2接口,并且可以顺便修改cookie中domain信息,方便当前域cookie写入,实现跨域登录。
先下载nginx,然后将nginx目录下的nginx.conf修改如下:
// proxy服务器
server {
listen 80;
server_name www.domain1.com;
location / {
proxy_pass http://www.domain2.com:8080; #反向代理
proxy_cookie_domain www.domain2.com www.domain1.com; #修改cookie里域名
index index.html index.htm;
# 当用webpack-dev-server等中间件代理接口访问nignx时,此时无浏览器参与,故没有同源限制,下面的跨域配置可不启用
add_header Access-Control-Allow-Origin http://www.domain1.com; #当前端只跨域不带cookie时,可为*
add_header Access-Control-Allow-Credentials true;
}
}
最后通过命令行nginx -s reload启动nginx
// index.html
var xhr = new XMLHttpRequest();
// 前端开关:浏览器是否读写cookie
xhr.withCredentials = true;
// 访问nginx中的代理服务器
xhr.open('get', 'http://www.domain1.com:81/?user=admin', true);
xhr.send();
// server.js
var http = require('http');
var server = http.createServer();
var qs = require('querystring');
server.on('request', function(req, res) {
var params = qs.parse(req.url.substring(2));
// 向前台写cookie
res.writeHead(200, {
'Set-Cookie': 'l=a123456;Path=/;Domain=www.domain2.com;HttpOnly' // HttpOnly:脚本无法读取
});
res.write(JSON.stringify(params));
res.end();
});
server.listen('8080');
console.log('Server is running at port 8080...');
window.name属性的独特之处:name值在不同的页面(甚至不同域名)加载后依旧存在,并且可以支持非常长的 name 值(2MB)。
其中a.html和b.html是同域的,都是http://localhost:3000
;而c.html是http://localhost:4000
// a.html(http://localhost:3000/b.html)
<iframe src="http://localhost:4000/c.html" frameborder="0" onload="load()" id="iframe"></iframe>
<script>
let first = true
// onload事件会触发2次,第1次加载跨域页,并留存数据于window.name
function load() {
if(first){
// 第1次onload(跨域页)成功后,切换到同域代理页面
let iframe = document.getElementById('iframe');
iframe.src = 'http://localhost:3000/b.html';
first = false;
}else{
// 第2次onload(同域b.html页)成功后,读取同域window.name中数据
console.log(iframe.contentWindow.name);
}
}
</script>
b.html为中间代理页,与a.html同域,内容为空。
// c.html(http://localhost:4000/c.html)
<script>
window.name = '我不爱你'
</script>
总结:通过iframe的src属性由外域转向本地域,跨域数据即由iframe的window.name从外域传递到本地域。这个就巧妙地绕过了浏览器的跨域访问限制,但同时它又是安全操作。
实现原理: a.html欲与c.html跨域相互通信,通过中间页b.html来实现。 三个页面,不同域之间利用iframe的location.hash传值,相同域之间直接js访问来通信。
具体实现步骤:一开始a.html给c.html传一个hash值,然后c.html收到hash值后,再把hash值传递给b.html,最后b.html将结果放到a.html的hash值中。
同样的,a.html和b.html是同域的,都是http://localhost:3000
;而c.html是http://localhost:4000
// a.html
<iframe src="http://localhost:4000/c.html#iloveyou"></iframe>
<script>
window.onhashchange = function () { //检测hash的变化
console.log(location.hash);
}
</script>
// b.html
<script>
window.parent.parent.location.hash = location.hash
//b.html将结果放到a.html的hash值中,b.html可通过parent.parent访问a.html页面
</script>
// c.html
console.log(location.hash);
let iframe = document.createElement('iframe');
iframe.src = 'http://localhost:3000/b.html#idontloveyou';
document.body.appendChild(iframe);
该方式只能用于二级域名相同的情况下,比如 a.test.com 和 b.test.com 适用于该方式。
只需要给页面添加 document.domain ='test.com' 表示二级域名都相同就可以实现跨域。
实现原理:两个页面都通过js强制设置document.domain为基础主域,就实现了同域。
我们看个例子:页面a.zf1.cn:3000/a.html
获取页面b.zf1.cn:3000/b.html
中a的值
// a.html
<body>
helloa
<iframe src="http://b.zf1.cn:3000/b.html" frameborder="0" onload="load()" id="frame"></iframe>
<script>
document.domain = 'zf1.cn'
function load() {
console.log(frame.contentWindow.a);
}
</script>
</body>
// b.html
<body>
hellob
<script>
document.domain = 'zf1.cn'
var a = 100;
</script>
</body>
Flex 是 Flexible Box 的缩写,意为"弹性布局",用来为盒状模型提供最大的灵活性。任何容器都可以指定为 Flex 布局。
注意,设为 Flex 布局以后,子元素的float、clear和vertical-align属性将失效。
采用 Flex 布局的元素,称为 Flex 容器(flex container),简称"容器"。它的所有子元素自动成为容器成员,称为 Flex 项目(flex item),简称"项目"。
简单的来说,容器就是外层,项目就是内层子元素。
flex-grow属性定义项目的放大比例,默认为0,即如果存在剩余空间,也不放大。
flex-shrink属性定义了项目的缩小比例,默认为1,即如果空间不足,该项目将缩小。
除了正常运行模式,ECMAscript 5添加了第二种运行模式:"严格模式"(strict mode)。顾名思义,这种模式使得Javascript在更严格的条件下运行。
进入"严格模式"的标志,是下面这行语句:
"use strict";
老版本的浏览器会把它当作一行普通字符串,加以忽略。
在正常模式中,如果一个变量没有声明就赋值,默认是全局变量。严格模式禁止这种用法,全局变量必须显式声明。
"use strict";
v = 1; // 报错,v未声明
for(i = 0; i < 2; i++) {
// 报错,i未声明
}
因此,严格模式下,变量都必须先用var命令声明,然后再使用。
function f(){
return !this;
}
// 返回false,因为"this"指向全局对象,"!this"就是false
function f(){
"use strict";
return !this;
}
// 返回true,因为严格模式下,this的值为undefined,所以"!this"为true。
因此,使用构造函数时,如果忘了加new,this不再指向全局对象,而是报错。
function f() {
"use strict";
this.a = 1;
};
f(); // 报错,this未定义
我们假设计算机运行一行基础代码需要执行一次运算。
int aFunc(void) {
printf("Hello, World!\n"); // 需要执行 1 次
return 0; // 需要执行 1 次
}
那么上面这个方法需要执行 2 次运算
int aFunc(int n) {
for(int i = 0; i<n; i++) { // 需要执行 (n + 1) 次
printf("Hello, World!\n"); // 需要执行 n 次
}
return 0; // 需要执行 1 次
}
这个方法需要 (n + 1 + n + 1) = 2n + 2 次运算。
我们把 算法需要执行的运算次数 用 输入大小n 的函数 表示,即 T(n) 。
此时为了 估算算法需要的运行时间 和 简化算法分析,我们引入时间复杂度的概念。
定义:存在常数 c 和函数 f(N),使得当 N >= c 时 T(N) <= f(N),表示为 T(n) = O(f(n)) 。
如图:
当 N >= 2 的时候,f(n) = n^2 总是大于 T(n) = n + 2 的,于是我们说 f(n) 的增长速度是大于或者等于 T(n) 的,也说 f(n) 是 T(n) 的上界,可以表示为 T(n) = O(f(n))。
因为f(n) 的增长速度是大于或者等于 T(n) 的,即T(n) = O(f(n)),所以我们可以用 f(n) 的增长速度来度量 T(n) 的增长速度,所以我们说这个算法的时间复杂度是 O(f(n))。
算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述
显然如果 T(n) = n^2,那么 T(n) = O(n^2),T(n) = O(n^3),T(n) = O(n^4) 都是成立的,但是因为第一个 f(n) 的增长速度与 T(n) 是最接近的,所以第一个是最好的选择,所以我们说这个算法的复杂度是 O(n^2) 。
那么当我们拿到算法的执行次数函数 T(n) 之后怎么得到算法的时间复杂度呢?
比如
第一个 Hello, World 的例子中 T(n) = 2,所以我们说那个函数(算法)的时间复杂度为 O(1)。
T(n) = n + 29,此时时间复杂度为 O(n)。
比如
T(n) = n^3 + n^2 + 29,此时时间复杂度为 O(n^3)。
比如
T(n) = 3n^3,此时时间复杂度为 O(n^3)。
综合起来:如果一个算法的执行次数是 T(n),那么只保留最高次项,同时忽略最高项的系数后得到函数 f(n),此时算法的时间复杂度就是 O(f(n))。为了方便描述,下文称此为 大O推导法
由此可见,由执行次数 T(n) 得到时间复杂度并不困难,很多时候困难的是从算法通过分析和数学运算得到 T(n)。对此,提供下列四个便利的法则,这些法则都是可以简单推导出来的,总结出来以便提高效率。
void aFunc(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
}
}
// 此时时间复杂度为 O(n × 1),即 O(n)。
void aFunc(int n) {
for(int i = 0; i < n; i++) { // 循环次数为 n
for(int j = 0; j < n; j++) { // 循环次数为 n
printf("Hello, World!\n"); // 循环体时间复杂度为 O(1)
}
}
}
// 此时时间复杂度为 O(n × n × 1),即 O(n^2)。
void aFunc(int n) {
// 第一部分时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
// 第二部分时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("Hello, World!\n");
}
}
// 此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。
void aFunc(int n) {
if (n >= 0) {
// 第一条路径时间复杂度为 O(n^2)
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
printf("输入数据大于等于零\n");
}
}
} else {
// 第二条路径时间复杂度为 O(n)
for(int j = 0; j < n; j++) {
printf("输入数据小于零\n");
}
}
}
// 此时时间复杂度为 max(O(n^2), O(n)),即 O(n^2)。
时间复杂度分析的基本策略是:从内向外分析,从最深层开始分析。如果遇到函数调用,要深入函数进行分析
最后,我们来练习一下
求该方法的时间复杂度
void aFunc(int n) {
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
printf("Hello World\n");
}
}
}
参考答案:
当 i = 0 时,内循环执行 n 次运算,当 i = 1 时,内循环执行 n - 1 次运算……当 i = n - 1 时,内循环执行 1 次运算。
所以,执行次数 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。
根据上文说的 大O推导法 可以知道,此时时间复杂度为 O(n^2)。
求该方法的时间复杂度
void aFunc(int n) {
for (int i = 2; i < n; i++) {
i *= 2;
printf("%i\n", i);
}
}
参考答案:
假设循环次数为 t,则循环条件满足 2^t < n。
可以得出,执行次数t = log(2)(n),即 T(n) = log(2)(n),可见时间复杂度为 O(log(2)(n)),即 O(log n)。
求该方法的时间复杂度
long aFunc(int n) {
if (n <= 1) {
return 1;
} else {
return aFunc(n - 1) + aFunc(n - 2);
}
}
参考答案:
显然运行次数,T(0) = T(1) = 1,同时 T(n) = T(n - 1) + T(n - 2) + 1,这里的 1 是其中的加法算一次执行。
显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列,通过归纳证明法可以证明,当 n >= 1 时 T(n) < (5/3)^n,同时当 n > 4 时 T(n) >= (3/2)^n。
所以该方法的时间复杂度可以表示为 O((5/3)^n),简化后为 O(2^n)。
可见这个方法所需的运行时间是以指数的速度增长的。如果大家感兴趣,可以试下分别用 1,10,100 的输入大小来测试下算法的运行时间,相信大家会感受到时间复杂度的无穷魅力。
作者:raymondCaptain
链接:https://www.jianshu.com/p/f4cca5ce055a
來源:简书
简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。
说到 JS 的变量提升,首先要提到 JS 里面函数的两种声明方式存在的坑
function fn(){} //函数声明式
var fn = function(){}; //函数表达式
对于函数声明式,解析器会确保在所有代码执行之前声明已经被解析。
而对于函数表达式,与定义其它基本类型变量一样,逐句执行并解析。
(function (){
console.log(foo);
var foo = "Javascript";
})();
// 输出 undefined
会被解释成
(function (){
var foo;
console.log(foo);
foo = "Javascript";
})();
/* 函数声明式 */
(function(){
fn();
function fn() {
console.log('来自函数声明式fn');
}
})();
/* 函数表达式 */
(function(){
fn();
var fn = function() {
console.log('来自函数表达式fn');
}
})();
// 输出
// 来自函数声明式fn
// fn is not a function
以下输出什么
(function() {
var a = b = 5;
})();
console.log(b); // 5
这个问题的陷阱就是,在立即执行函数表达式(IIFE)中,有两个赋值,但是其中变量 a
使用关键词 var
来声明。这就意味着 a
是这个函数的局部变量。与此相反,b
被分配给了全局作用域(译注:也就是全局变量)。
这个问题另一个陷阱就是,在函数中没有使用”严格模式” ('use strict';)。如果 严格模式开启,那么代码就会报错 ” Uncaught ReferenceError: b is not defined” 。
严格模式下应该这么写
(function() {
'use strict';
var a = window.b = 5;
})();
console.log(b);
function Foo() {
getName = function(){ alert(1); };
return this;
}
Foo.getName = function() { alert(2); };
Foo.prototype.getName = function(){ alert(3); };
var getName = function() { alert(4); };
function getName(){ alert(5); }
Foo.getName(); // ?
getName(); // ?
Foo().getName(); // ?
getName(); // ?
new Foo.getName(); // ?
new Foo().getName(); // ?
new new Foo().getName(); // ?
// 参考 https://www.jianshu.com/p/df11f3ba355c
var fullname = 'John Doe';
var obj = {
fullname: 'Colin Ihrig',
prop: {
fullname: 'Aurelio De Rosa',
getFullname: function() {
return this.fullname;
}
}
};
console.log(obj.prop.getFullname()); // Aurelio De Rosa
var test = obj.prop.getFullname;
console.log(test()); // John Doe
Aurelio De Rosa
console.log(test.call(obj.prop));
var foo = 1;
function bar () {
if (!foo) {
var foo = 10;
}
console.log(foo);
}
bar();
var foo = 1;
var foo=1;
function bar(){
if(!foo) {
foo=10;
}
console.log(foo);
}
bar();
function bar(){
if(!foo) {
foo=10;
}
console.log(foo);
}
bar();
函数会首先被提升,然后跟着才是变量。也就是说同时存在函数声明与函数表达式时,函数声明会优先于函数表达式提升。
foo();
function foo() {
console.log('1');
}
var foo = function () { console.log('2'); }
实际上会被解析为
function foo() {
console.log('1');
}
var foo;
foo();
foo = function () { console.log('2'); }
强制类型转换的特例
var a = "false"
var b = "0"
var c = "''"
var d = Boolean(a && b && c) // true
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.